运维开发网

详细介绍了C语言动态规划的背包问题

运维开发网 https://www.qedev.com 2022-05-13 17:47 出处:网络
这篇文章主要介绍了C语言动态规划之背包问题详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧 01背包问题

这篇文章主要介绍了C语言动态规划之背包问题详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧 01背包问题

给定n种物品和一个容量为C的背包,物品I的重量为w[i],价值为v[i]。问:如何选择装入背包的物品,使背包的总价值最大化?(面对每一个武平,你只能选择拿还是不拿。不能选择加载一个物品的一部分,也不能多次加载一个物品。)

声明一个数组f[n][c]的二维数组,f[i][j]表示在面对第i件物品,且背包容量为j时所能获得的最大价值。 根据题目要求进行打表查找相关的边界和规律 根据打表列写相关的状态转移方程 用程序实现状态转移方程

实践练习:

一个旅行者有一个最多能装100公斤的背包.现在有N个项目,它们的权重是W1,W2,W3,W4,…,Wn。它们的价值分别是C1、C3、C2、…、Cn,让旅行者获得最大价值。

输入描述:

第一行:两个整数,m(背包容量,Mlt= 200)和n(项目数,Nlt=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 0 0 0 2 1 1 1 1 3 0 0 0 1 3 3 3 4 4 4 5 0 1 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 lt;stdio.hgt;int max(const int a,const int b){ return agt;b #63; a:b;}int main(){ int w为了庆祝班级在校运会上获得第一名,班主任决定举办庆功宴,并拨款为运动员购买奖品。预计分配的金额可以买到最大价值的奖品,可以补充自己的精力和体力。={0},v[35]={0},dp[35][210]={0}; int n,m; scanf("%d %d",amp;m,amp;n); int i,j; for(i=1;ilt;=n;i++){ scanf("%d %d",amp;w[i],amp;v[i]); } for(i=1;ilt;=n;i++){ for(j=1;jlt;=m;j++){ if(jgt;=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;klt;=n;k++) { for(int l=0;llt;=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 lt;stdio.hgt;int max(const int a,const int b){ return agt;b #63; a:b;}int main(){ int w[35]={0},v[35]={0},dp[210]={0}; int n,m; scanf("%d %d",amp;m,amp;n); int i,j; for(i=1;ilt;=n;i++){ scanf("%d %d",amp;w[i],amp;v[i]); } for(i=1;ilt;=n;i++){ for(j=m;jgt;=0;j--){ if(jgt;=w[i])//如果当前背包的容量大于商品的质量 { dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//判断是否应该拿下 } } for(int k=0;klt;=m;k++) { printf("%d ",dp[k]); } printf("\n"); } printf("%d\n",dp[n][m]);}


可以看出和上面的dp表输出没什么区别!

完全背包问题

标题描述:

有n种物品,每种物品都有一个重量和一个数值,但是每种物品的数量是无限的。有一个背包,最大载重量为M,现在从N中选取若干物品(同一物品可多次选取),使其质量小于等于M,取值之和最大。

输入:

第一行:两个整数,m(背包容量,Mlt= 200)和n(项目数,Nlt=30);
第2行…N+1:每行两个整数Wi,Ci,表示每件物品的质量和价值。

输出:

只有一行,一个数字,表示最大总价值。

示例:

输入:10 42 13 34 57 9输出:12

和01背包问题不同的是,它不是每个物品带不带的问题,而是选择几个物品,最后选择价值最大的一个。那么我们可以在01背包上继续思考这个问题。在01背包里,我们知道了之前的状态,我只要判断要不要拿K物品,和没拿的对比就行了。如果价值比以前更大,我会买下它们。而且每种最多只能带j/w[i]个物品,所以加个重循环就行了!该程序的核心代码如下:

for(i=1;ilt;=n;i++){ for(j=m;jgt;=0;j--){ for(k=0;klt;=j/w[i];k++) { dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);//判断是否应该拿下k个商品 } }}

通过代码可以发现,这个简单的算法需要三重循环,看起来时间复杂度很高。然后我们也借鉴01背包观看完整的背包!

W[i](质量)v[i](价值)0 1 2 3 4 5 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 2 3 4 5 3 3 3 0 0 1 3 4 6 7 9 4 5 0 1 3 5 6 8 8 10 11 7 9 0 1 5 6 9 10 12

根据表中红色标注的数值,需要注意的是,如果背包的容量装不下目前物品的质量。那么当前容量所能容纳的最有价值的物品就等于最后一个物品所能容纳的最大值。重点说说4是怎么来的。这个4不是从i-1来的,而是从I来的,用正序推导出该项的值。状态转移方程可以写成:DP [I] [J] = max (DP [I-1] [J],DP [I] [J-W [I]]+V [I])和01背包唯一的区别就是max的第二个参数。01背包是i-1,而完全背包是I,是正序推理得到的状态转移方程。

根据状态转移方程,程序应该快写好了!但是根据dp的后失效原理,动态规划的状态转移方程是压缩的!压缩后为DP [J] = Max (DP [J],DP [J-W [I]]+V [I])。小伙伴们,看看是不是和01背包的状态转移方程一模一样!但两者有一个显著的区别:01背包使用的是前一个的数据,因此需要进行反转,以避免覆盖之前的值,而完整的背包则是从当前更新的数据进行相关操作。通过以上分析,我们可以编写以下程序:

#include lt;stdio.hgt;int max(const int a,const int b){ return agt;b #63; a:b;}int main(){ int w[35]={0},v[35]={0},dp[210]={0}; int n,m; scanf("%d %d",amp;m,amp;n); int i,j; for(i=1;ilt;=n;i++){ scanf("%d %d",amp;w[i],amp;v[i]); } for(i=1;ilt;=n;i++){ for(j=0;jlt;=m;j++){ if(jgt;=w[i])//如果当前背包的容量大于商品的质量 { dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//判断是否应该拿下 } } for(int k=0;klt;=m;k++) { printf("%d ",dp[k]); } printf("\n"); } printf("%d\n",dp[m]);}


从上面代码的输出可以看出,打印出来的dp表和我们推测的没有区别,程序是正确的!

多重背包问题

标题描述:

[35]

输入:

在第一行输入两个数字n(NLT;=500),m(MLT;=6000),其中n代表要购买的奖品数量,m代表分配金额。

接下来的n行,每行3个数字,w、V、s V、S分别代表I奖的价格、价值(价格和价值是不同的概念)和可购买的最大数量(0到S件可购买),其中wlt=100,vlt=1000,slt=10;

输出:

Line:一个数字,表示你这次购买可以获得的最大价值(注意!不是价格)。

示例:

输入:
5 1000
输出:
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

与完整背包不同的是,完整背包的物品数量不限,而多个背包只能带指定数量的物品。那么想到的最简单的办法就是把相同的物品分开。比如有N个A项,分成a1 a2 a3 a4…an然后用01背包法求解。然后我们可以编写下面的核心代码:

for(i=1;ilt;=n;i++){ for(j=m;jgt;=0;j--){ for(k=0;klt;=s[i]amp;amp;jgt;=k*w[i];k++) { dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);//从01背包的状态转移方程,去增加第i个物品拿k个的循环 } }}

从上面的代码可以看出,当s[i]极大时,会消耗大量的时间复杂度,所以一定有优化的方法!然后我们可以优化二进制应该取多少相同的项。我们可以通过以下问题进行研究:

有1000个苹果。你怎么把它们放在10个盒子里?无论我想带多少苹果,我都可以用盒子带。

用二进制的思路是每个方框代表二进制对应的位数,所以210 > 1024应该可以满足题目的条件。那么每个盒子里的苹果是1,2,4,8,16,32,…488(1000-512)。第一箱需要一个苹果,第二件需要两个苹果,一两箱需要三个苹果。那么对于拿1000盒的问题,应该是回收了1000次。优化后只能循环使用10次!然后我们就可以写下面的程序了!

for(i=1;ilt;=n;i++){ for(j=m;jgt;=0;j--){ for(k=0;klt;=s[i]amp;amp;jgt;=k*w[i];klt;lt;=1) { if((klt;lt;1)gt;s[i]amp;amp;jgt;=k*w[i]) { dp[j]=max(dp[j],dp[j-(s[i]-k)*w[i]]+(s[i]-k)*v[i]); } else dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);//从01背包的状态转移方程,去增加第i个物品拿k个的循环 } }}动态规划解题思路

我们对动态编程的一般想法如下:

判断是动态规划的解题思路以后立马定义一个数组,把数组对应的下标、对应的值想清楚。 然后根据题目意思找规律进行打表,找出初始状态以及一些边界条件。 根据打表的数据找出状态转移方程。 最后根据状态转移方程进行编写程序。

至此,本文对C语言动态规划背包问题的详细解释已经介绍到这里。关于C语言背包的更多信息

0

精彩评论

暂无评论...
验证码 换一张
取 消