计科院20级刘磊

用户名：1579364808

访问量：4389

签　名：

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

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

　　自我简介：

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

TA的其他文章

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

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

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

　　作者: 计科院20级刘磊　　　　发表时间：2021-05-12 21:29:21 浏览：648　|　评论：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分

6 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科院20级刘磊

TA的其他文章

你可能喜欢

假币问题（C语言代码）

【偶数求和】（C语言代码）记得sum的归零时机

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

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

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

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

最小公倍数（C语言代码）

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

三角形（C++代码）递推

矩阵加法（C语言代码）

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

字符串比较（C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

Manchester-汽水瓶问题

计科院20级刘磊

TA的其他文章

你可能喜欢

假币问题 （C语言代码）

【偶数求和】 （C语言代码）记得sum的归零时机

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

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

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

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

最小公倍数 （C语言代码）

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

三角形 （C++代码）递推

矩阵加法 （C语言代码）

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

字符串比较 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

Manchester-汽水瓶问题

假币问题（C语言代码）

【偶数求和】（C语言代码）记得sum的归零时机

　　评论区

最小公倍数（C语言代码）

三角形（C++代码）递推

矩阵加法（C语言代码）

字符串比较（C语言代码）