计科院20级刘磊

用户名：1579364808

访问量：3740

签　名：

写代码困了，就喝杯Java咖啡提提神

等　　级
排　　名	2457
经　　验	2201
参赛次数	6
文章发表	16
年　　龄	19
在职情况	学生
学　　校	怀化学院
专　　业	计算机科学与技术

　　自我简介：

计算机科学与技术专业的一名小码农

TA的其他文章

回溯法解决全排列
浏览：107

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

01背包问题-DP--c语言

　　作者: 计科院20级刘磊　　　　发表时间：2021-05-12 21:29:21 浏览：612　|　评论：0　

原题链接：信息学奥赛一本通T1267-01背包问题

**
基本思路**
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即 F[i, v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转移方程便是：
F[i, v] = max{F[i − 1, v], F[i − 1, v − Ci] + Wi}
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所
以有必要将它详细解释一下：“将前 i 件物品放入容量为 v 的背包中”这个子问题，若
只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只和前 i − 1 件物品相关
的问题。如果不放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入容量为 v 的背
包中”，价值为 F[i − 1, v]；如果放第 i 件物品，那么问题就转化为“前 i − 1 件物品放
入剩下的容量为 v − Ci 的背包中”

```c

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N=32,MAX_M=301;
int w[MAX_N],c[MAX_N];
int m,n;
int dp[MAX_N][MAX_M]; //前 i 件物品恰放入一个容量为j的背包可以获得的最大价值

void output(int m,int n)
{
    for(int j = 0; j<=m; j++)
    {
   dp[0][j]=0;//没有物品时，总的价值为0
    }
	for(int i = 0; i<=n; i++)
    {
   dp[0][j]=0;//背包最大容量为0时，总的价值为0
    }
	
	//上面两个for循环可以不写，因为全局变量初始化为0
    for(int i=1; i<=n; i++)
    {
        for(int j= 1; j<=m; j++)
        {
            if(w[i]>j)
            {
                dp[i][j]=dp[i-1][j];//背包放不进物品i
            }
            else//背包总能放入物品i的情况
            {
                dp[i][j]= max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);//考虑j容量的背包中是否加入第i件物品，有两种情况，取最大值.如不不加入，则从前i-1件中选装入容量为j的背包；如果加入，则从前i-1件中选物品，装入容量为j-w[i]的背包(因为背包中已经含有第i件物品了)
            }
        }
    }
    printf("%d",dp[n][m]);
}

int main()
{
    scanf("%d%d",&m,&n);
    for(int i = 1; i<=n; i++)//索引从1开始，如果从0开始，则放背包时重量和价值索引记得减去1
    {
        scanf("%d%d",&w[i],&c[i]);
    }
    output(m,n);
    return 0;
}

```

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

计科院20级刘磊

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C二级辅导-进制转换（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

01背包问题-DP--c语言

评论区

精彩推荐

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

大神老白（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

小明A+B （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

【蟠桃记】（C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

IP判断（C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

计科院20级刘磊

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C二级辅导-进制转换 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

01背包问题-DP--c语言

评论区

精彩推荐

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

大神老白 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

小明A+B （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

【蟠桃记】 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

IP判断 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

大神老白（C语言代码）

【蟠桃记】（C语言代码）

IP判断（C语言代码）