这篇文章主要介绍了C语言动态规划之背包问题详解，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
01背包问题
给定n种物品，和一个容量为C的背包，物品i的重量是w[i],其价值为v[i]。问如何选择装入背包的物品，使得装入背包中的总价值最大？（面对每个武平，只能有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入物品多次）
- 声明一个数组
f[n][c]的二维数组，f[i][j]表示在面对第i件物品，且背包容量为j时所能获得的最大价值。 - 根据题目要求进行打表查找相关的边界和规律
- 根据打表列写相关的状态转移方程
- 用程序实现状态转移方程
真题演练：
一个旅行者有一个最多能装M公斤的背包，现在有n件物品，它们的重量分别是W1、W2、W3、W4、…、Wn。它们的价值分别是C1、C3、C2、…、Cn,求旅行者能获得最大价值。
输入描述：
第一行：两个整数，M（背包容量，M<= 200)和N（物品数量，N<=30);
第2…N+1行：每行两个整数Wi，Ci，表示每个物品的质量与价值。
输出描述：
仅一行，一个数，表示最大总价值
样例：
输入：
10 4
2 1
3 3
4 5
7 9
输出：
12
解题步骤
定义一个数组dp[i][j]表示容量为j时，拿第i个物品时所能获取的最大价值。
按照题目要求进行打表，列出对应的dp表。
| W[i]（质量） | V[i]（价值） | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 2 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | 3 | 0 | 0 | 1 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 |
| 4 | 5 | 0 | 0 | 1 | 3 | 5 | 5 | 6 | 8 | 8 | 9 | 9 |
| 7 | 9 | 0 | 0 | 1 | 3 | 5 | 5 | 6 | 9 | 9 | 10 | 12 |
对于一个动态规划问题设置下标时最好从0开始，因为动态规划经常会和上一个状态有关系！从上面的dp表可以看出来对于一个物品我们拿还是不难需要进行两步来判断。第一步：判断背包当前的容量j是否大于物品当前的质量，如果物品的质量大于背包的容量那么就舍弃。第二步：如果背包可以装下这个物品，就需要判断装下该物品获取的最大价值是不是大于不装下这个物品所获取的最大价值，如果大于那么就把东西装下！根据这样的思想我们可以得到状态转移方程：
如果单签背包的容量可以装下物品:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
如果当前背包的容量装不下该物品:
dp[i][j]=dp[i-1][j];
#include int max(const int a,const int b) { return a>b ? a:b; } int main() { int w[35]={0},v[35]={0},dp[35][210]={0}; int n,m; scanf("%d %d",&m,&n); int i,j; for(i=1;i<=n;i++){ scanf("%d %d",&w[i],&v[i]); } for(i=1;i<=n;i++){ for(j=1;j=w[i])//如果当前背包的容量大于商品的质量 { dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//判断是否应该拿下 } else//大于背包的当前容量 { dp[i][j]=dp[i-1][j]; } } } for(int k=0;k<=n;k++) { for(int l=0;l<=m;l++) { printf("%d ",dp[k][l]); } printf("\n"); } printf("%d\n",dp[n][m]); }
通过运行以上程序可以看到最终的输出dp表和我们的预期是相符合的！但是并没有结束，动态规划有一个后无效性原则(当前状态只与前一个状态有关)。那么我们就可以对dp数组进行压缩处理，将二维数组转换成一维数组。每一次选择物品对这个数组进行更新就可以啦！那么就可以将状态转移方程压缩成为 dp[j]=max(dp[j],dp[j-w[i]]+v[i]) 。不过我们需要注意的是在压缩过后我们需要逆序刷新数组的值，如果正序刷新的话就不能保存上一个阶段对应获取最大价值的值了。那么我们就可以写出以下程序：
#include int max(const int a,const int b) { return a>b ? a:b; } int main() { int w[35]={0},v[35]={0},dp[210]={0}; int n,m; scanf("%d %d",&m,&n); int i,j; for(i=1;i<=n;i++){ scanf("%d %d",&w[i],&v[i]); } for(i=1;i=0;j--){ if(j>=w[i])//如果当前背包的容量大于商品的质量 { dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//判断是否应该拿下 } } for(int k=0;k<=m;k++) { printf("%d ",dp[k]); } printf("\n"); } printf("%d\n",dp[n][m]); }
可以看出和上面输出的dp表并没有什么区别！
完全背包问题
题目描述：
设有n种物品，每种物品有一个重量及一个价值，但每种物品的数量都是无限的，有一个背包，最大载重量为m，今从n中物品中选取若干件（同一种物品可以多次选取）使其质量小于等于m，而价值的和为最大。
输入：
第一行：两个整数，M（背包容量，M<= 200)和N（物品数量，N<=30);
第2…N+1行：每行两个整数Wi，Ci，表示每个物品的质量与价值。
输出：
仅一行，一个数，表示最大总价值。
样例：
输入: 10 4 2 1 3 3 4 5 7 9 输出: 12
与01背包问题不同的是这不是每个物品选择拿与不拿的问题了，而是要选择几个该物品，最终选择价值最大的。那么我们可以在01背包的问题上继续进行思考这个问题，01背包中我们知道了之前的状态，那么我无非就是要判断拿k个物品和不拿时进行比较，如果价值比之前大就拿下。而每个种类的物品最多只能拿取j/w[i]个，再加一重循环不就可以啦！程序的核心代码如下：
for(i=1;i=0;j--){ for(k=0;k<=j/w[i];k++) { dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i])<span style="color:transparent">来源gaodai#ma#com搞*代#码网</span>;//判断是否应该拿下k个商品 } } }
通过代码可以发现通过这种朴素的算法是需要三重循环的，好像对时间复杂度比较高。那么我们也借鉴01背包来对完全背包进行打表！
| w[i]（质量） | v[i]（价值） | 0 | 1 | 2 | 3 | 4 | 5 | 6
以上就是C语言动态规划之背包问题详解的详细内容，更多请关注gaodaima搞代码网其它相关文章！ 搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：C语言动态规划之背包问题详解 |
|---|
