动态规划专题-背包讲解

2024-09-05 21:32
文章标签 动态 规划 讲解 背包 专题

本文主要是介绍动态规划专题-背包讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 01背包

    问题描述：

        有n件物品和一个容量为v的背包。放入第i件物品的占的空间为Ci,得到的价值是Wi,求解将哪些物品装入背包可以

         使得总价值最大；

        首先要明白这个问题不能用贪心来做，因为当前的选择会影响到以后的选择，也就是说当前的选择的最优解

        可能会影响到全局的最优解；

       考虑用动态规划来做

           1.定义状态：

                    定义状态dp[i][j]为前i件物品恰放入容量为j的背包时的最大价值；

                    那么dp[n][v]就是这个问题的最终解；

           2.描述不同状态如何转移： 

                     在这个过程中，我们很自然想到的决策就是第i件物品放还是不放；放与不放会直接影响到dp[i][j]的值；

                    1.放，那么dp[i][j]的状态可由dp[i-1][j-Ci] + Wi转移过来

                    2.不放，那么dp[i][j]的状态可由dp[i-1][j]转移过来

                    我们所要做的就是在这两种决策中选取一种最优的；

                      所以状态转移方程为dp[i][j] = max(dp[i-1][j-Ci] + Wi , dp[i-1][j]);

            3.按一个方向求出该问题的解

                     状态dp[i][j]总是要取决于之前的状态dp[i-1][j-Ci] + Wi,dp[i-1][j],所以我们应按按自底而上的方向求解

 

      当然，除了这种状态，我们可以定义另外一种状态来解决01背包问题

            1.定义状态：

                    定义状态dp[i][j]为前i个物品中价值为j时的耗费的最小空间；

             2.描述不同状态如何转移：

                    在这个过程中，我们能够很自然的想到当前物品的选与不选会影响当前状态；

                    1.放，那么状态dp[i][j]的状态可由状态dp[i-1][j-W[i]] + C[i]转移过来

                    2.不放，那么状态dp[i][j]的状态可由状态dp[i-1][j]转移过来

                     所以状态转移方程为dp[i][j] = min(dp[i-1][j-W[i] + C[i] , dp[i-1][j]);

             3.自底而上的求解

                    注意初始化，dp[0][0]为[0],dp[0][j]为不合法的状态，用一个无穷大的数代替；

                    在把所有状态求出来之后，我们只需要找出dp[n][j]不大于V的最大j值即可

 

两种不同状态的代码如下：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;const int INF = 2005;
int dp[INF][INF];	//定义状态dp[i][j]为前i件物品放入容量为j的背包时的最大价值；
int W[INF],C[INF];int main()
{int n, v;scanf("%d%d",&n,&v);for(int i = 1; i <= n; i++){scanf("%d",&W[i]);}for(int i = 1; i <= n; i++){scanf("%d",&C[i]);}memset(dp,0,sizeof(dp));		//初始化 for(int i = 1; i <= n; i++)		//自底而上的求解 {for(int j = 0; j <= v; j++){if(j >= C[i]){dp[i][j] = max(dp[i-1][j],dp[i-1][j - C[i]] + W[i]);	//状态转移 }else{dp[i][j] = dp[i-1][j];}}}printf("%d\n",dp[n][v]);return 0;
} 
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF = 2005;int dp[INF][INF];		//定义状态dp[i][j]为前i个物品中价值为j时的耗费的最小空间；//这种状态只适用于C[i]的值很大，而W[i]的值较小的情况 int W[INF],C[INF];int main()
{int T;scanf("%d",&T);int n, v;scanf("%d%d",&n,&v);for(int i = 1; i <= n; i++){scanf("%d",&W[i]);}for(int i = 1; i <= n; i++){scanf("%d",&C[i]);}memset(dp,0,sizeof(dp));	//初始化 for(int i = 1; i < INF; i++){dp[0][i] = INF + 5;}for(int i = 1; i <= n; i++){for(int j = 0; j <= INF; j++) {if(j >= W[i]){dp[i][j] = min(dp[i-1][j],dp[i-1][j - W[i]] + C[i]);	//状态转移方程 }else{dp[i][j] = dp[i-1][j];}}}int res = -1;for(int j = 0; j < INF; j++)if(dp[n][j] <= v)	//根据定义的状态可得结果是dp[n][j]不大于V的最大j值即可 {res = j;}printf("%d\n",res);return 0;
}

 

01背包代码在时间上不能被优化，但在空间上可以优化，具体如何优化，这里不再讲解，想了解的自行百度

 

 

————————————————————————————————————————————————————

2.完全背包

问题描述：

        有n种物品和一个容量为v的背包，每种物品都有无限件可用，放入第i种物品的费用是Ci,价值是Wi;问如何装才能使

        总价值最大；

        仔细看这个问题，会发现这个问题和01背包类似，01背包是有n种物品，每种只有1件；所以我们可以根据01背包

        的策略来做；

        定义状态dp[i][j]为前i种物品恰放入容量为j的背包时的最大价值；

        在01背包中，对于每一种物品来说，策略是取0件或是取1件。在完全背包中，对于每一种物品来说，相关的策略是

        取0件，取1件，取2件，取3件......取v/Ci(知道背包装不下为止)，类比01背包，我们所要做的就是在这些策略选择一

        个最优的；

        所以这个状态转方程为：

        dp[i][j] = max(dp[i-1][j-k*Ci] + k*Wi) k*Ci <= v;

        这种方法的代码为：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int INF = 1005;int dp[INF][INF];   //定义状态dp[i][j]为前i件物品恰放入容量为j的背包时的最大价值；
int main()
{int n,v;while(~scanf("%d%d",&n,&v)){int W[INF + 5],C[INF + 5];for(int i = 1; i <= n; i++){scanf("%d %d",&C[i],&W[i]);} mmset(dp,0);		//初始化 for(int i = 1; i <= n; i++)			//自底而上的求解 {for(int j = 0; j <= v; j++){if(j >= C[i]){for(int k = 1; k * C[i] <= j; k++){dp[i][j] = max(dp[i][j],dp[i-1][j-k*C[i]] + k*W[i]);	//状态转移方程 }}else{dp[i][j] = dp[i-1][j];}}}printf("%d\n",dp[n][v]);}return 0;
}

        但是这种方法的时间复杂度比较高，所以考虑一下更好的方法；

        在上面中，策略是对于第i种物品，有取0件，取1件，取2件，取v/C[i]件。仔细想一下这个过程，我们就会发现

        对于每个dp[i][j],我们都要在从取1件开始，直到取到v/C[i]件。为什么要从取1件开始呢，因为我们不确定dp[i][j]

        的值从取第几件转移过来是最大的。所以我们要从取第1件开始试，一直试到放不下背包为止；

        我们再看一下是如何定义状态的，dp[i][j]是指 前i件物品恰放入容量为j的背包时的最大价值，注意两个词，"恰",

       "最大价值"，

        这说明dp[i][j]是指在空间为j的背包中，不能再装下任意一个前i种物品时，背包所能拥有的最大价值（仔细理解

        一下这句话，对接下来推导的状态转移方程有很大帮助）。

        所以对于dp[i][j]来说，如果只放1件第i种物品就能使dp[i][j]最大，那么一定是在dp[i][j - C[i]]的基础上放的.

        换句话说dp[i][j]是dp[i][j - ci]多放一件i物品转移过来的

        那么我们只需要在放不放这件物品进行决策，所以状态转移方程为：

        dp[i][j] = max(dp[i][j - C[i]] + W[i], dp[i-1][j]);    (有点绕，不懂的可以多想想)；

代码如下：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int INF = 1005;int dp[INF][INF];	//定义状态	
int main()
{int n,v;while(~scanf("%d%d",&n,&v)){int W[INF + 5],C[INF + 5];for(int i = 1; i <= n; i++){scanf("%d %d",&C[i],&W[i]);} mmset(dp,0);		//初始化 for(int i = 1; i <= n; i++){for(int j = 0; j <= v; j++){if(j >= C[i]){dp[i][j] = max(dp[i][j-C[i]] + W[i],dp[i-1][j]);	//状态转移方程 }else{dp[i][j] = dp[i-1][j];}}}printf("%d\n",dp[n][v]);}return 0;
}

    这个代码时间上很难在优化了，空间上可以优化，这里不再讲解，自己思考或者百度。

 

————————————————————————————————————————————————————

3.多重背包：

        问题描述：

            有n种物品和一个容量为v的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci,价值是Wi。求解：

            如何装才能使背包价值最大。

            仍然先把它转化为01背包来做。时间复杂度是O(n*v*(n*Mi)),时间复杂度是比较高的。

            考虑是否能优化：

            转化为01背包的思路是，第i种物品有Mi个，我们把这第i种物品的Mi个当成01背包来做。我们需要一件一件

            的放第i种物品，为什么要一件一件的放呢？(注意，这是优化的关键)，因为我们在放第Mi件物品时，必须要

            从前Mi-1件转移过来，如果没有前Mi-1件物品，我们就无法得到前Mi件物品的最优解。同理，在求前Mi-1

            的最优解，必须从前Mi-2转移过来。干说有些枯燥，我们来举个例子说明一下；

 

        有1种物品，共7件。一个空间为8的背包，每件物品耗费的空间是1，价值是1。问如何装才能使背包价值最大

            定义状态为dp[i][j]为前i件物品恰放入空间为j的背包时的最大价值。

            我们可以用一个图表来表示求这个问题时，dp[i][j]的变化：

            

可以看出dp[i]主要是比dp[i-1]多了蓝色部分；看出dp[2][2]是从dp[1][1]转移过来的

dp[3][3]是从dp[2][2]转移过来的；dp[4][4]是从dp[3][3]转移过来的.........

如果没有dp[2]，那么dp[3]的状态能求出来吗？（可以自己思考一下）

从dp[2]到dp[3]转移是放了一件物品，既然没有dp[2],我们可以在dp[1]上放2件物品来转移到dp[3]；

（注意，这点就相当于理解优化的关键）；

注意：可能有人会这样想，直接在dp[1]上加上6件物品，求这样出dp[7]这样会更快。但是这样是错的；

如果放6件物品，dp[7][2]只能从dp[1][-4]转移过来，显然是不合理的。

经过以上分析，我们意识到把一种物品拆分成多个物品时可行的。

我们可以用二进制的思想拆分物品，把个数为Mi个的物品拆分为

2^0, 2^1,2^2.......2^n, Mi - (2^(n+1)-1)个物品；

那么7就可以被分解为个数为1,2,4的物品；

如图

这就是拆分成多个物品的转移过程；

下图是拆分成多个物品后的dp[i][j]的状态

可以看出这个表的1，2，4行分别对应上表的1，3，7行；

可以发现我们把一个物品拆分成若干个二的次幂，可以使得后面的区间不重不漏的从前面转移过来；

代码如下：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int INF = 1005;int dp[INF][INF];		//定义状态 
int n,v,count1 = 1;
void ZeroPack(int w,int c);
int main()
{	int W[INF],C[INF],M[INF];scanf("%d%d",&n,&v);for(int i = 1; i <= n; i++){scanf("%d %d %d",&W[i],&C[i],&M[i]);}mmset(dp,0);			//初始化 for(int i = 1; i <= n; i++){int k = 1;int num = M[i];while(k < num)			//二进制拆分物品 {ZeroPack(W[i] * k,C[i] * k);num -= k;k <<= 1;}ZeroPack(W[i] * num,C[i] * num) ;}printf("%d\n",dp[count1-1][v]);return 0;
}
void ZeroPack(int w,int c)
{for(int j = 0; j <= v; j++){if(j >= c){dp[count1][j] = max(dp[count1-1][j],dp[count1-1][j - c] + w);}else{dp[count1][j] = dp[count1-1][j] ;}}count1++;
}

这个代码可以在空间上优化，也能在时间上优化；

时间上优化主要是当Ci * Mi >= v，这时候该种物品一定可以装满背包，可以这种物品看成完全背包来做；

空间上优化不再赘述；

————————————————————————————————————————————————————

————————————————————————————————————————————————————

至此，三种基础背包已经讲解完毕，但是还有一些细节上的问题需要注意：

关于背包有两种不同的问法：

第一种是：求背包的最大价值，上面讲的就是这个问题；

第二种是：求背包在装满的时候的最大价值；

关于第二种问法，我们只需要在初始化的时候，把dp[0][0]赋值为0，其他的dp[0][1~v]赋值为-OO(负无穷);

可以这样理解：

初始化的dp数组就是在没有装任何物品的合法状态。如果要求背包恰好装满，那么显然，只有容量为0的背包

是合法状态，因为他能满足当没有一件物品装入背包时“恰好装满”,其他的容量为1~v的背包都不满足，所以

是非法状态，用-OO表示；

如果只是要求背包的最大价值，并没有求装满，那么在初始化的时候dp[0][0~v]可以什么都不装，而且都是

合法状态，所以dp[0][0~v]初始化为0；

 

————————————————————————————————————————————————————

————————————————————————————————————————————————————

下面是三种背包空间优化过后的代码(主要是利用了滚动数组，这里只给出代码，不再讲解，请自行百度)

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a)) 
using namespace std;
const int INF = 10005;int dp[INF];
int n,v;	//物品的种类和背包的容量void ZeroPack(int w,int c) ;	//01背包
void CompletePack(int w,int c); 	//完全背包
void MultiplePack(int w,int c,int m) ;	//多重背包
int main()
{int W[INF],C[INF],M[INF];	//物品的价值，耗费的空间，件数scanf("%d %d",&n,&v);for(int i = 1; i <= n; i++){scanf("%d %d %d",&W[i],&C[i],&M[i]);} mmset(dp,0);		//注意初始化要根据问法不同而改变for(int i = 1; i <= n; i++){if(M[i] == 1) 	//属于01背包{ZeroPack(W[i],C[i]);} else if(C[i] * M[i] >= v)	//属于完全背包{CompletePack(W[i],C[i]);} else		//多重背包 {MultiplePack(W[i],C[i],M[i]) ;}} printf("%d\n",dp[v]);return 0;
}void ZeroPack(int w,int c)
{for(int j = v; j >= c; j--){dp[j] = max(dp[j],dp[j - c] + w);}
}void CompletePack(int w,int c)
{for(int j = c; j <= v; j++){dp[j] = max(dp[j],dp[j - c] + w);}}void MultiplePack(int w,int c,int m)
{if(c * m >= v){CompletePack(w,c);}else{int k = 1;while(k < m){ZeroPack(w*k,c*k);m -= k;k <<= 1; }ZeroPack(w*m,c*m);}}

 

 

 

 

 

            

            

            

 

        

        

        

        

 

        

 

       

 

      

     

        

 

 

这篇关于动态规划专题-背包讲解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1140118。

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
poj2576(二维背包)

poj2576(二维背包)

题意：n个人分成两组，两组人数只差小于1 ， 并且体重只差最小 对于人数要求恰好装满，对于体重要求尽量多，一开始没做出来，看了下解题，按照自己的感觉写，然后a了 状态转移方程：dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数，j表示背包容量，k表示输入的体重的 代码如下： #include<iostream>#include<
阅读更多...
hdu2159（二维背包）

hdu2159（二维背包）

这是我的第一道二维背包题，没想到自己一下子就A了，但是代码写的比较乱，下面的代码是我有重新修改的 状态转移：dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示，打了i个怪物，消耗j的耐力值，所得到的最大经验值 代码如下： #include<iostream>#include<algorithm>#include<
阅读更多...
csu(背包的变形题)

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物，m个人，每个人的魔法消耗和魔法伤害不同，求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...
hdu1171（母函数或多重背包）

hdu1171（母函数或多重背包）

题意：把物品分成两份，使得价值最接近 可以用背包，或者是母函数来解，母函数（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v） 其中指数为价值，每一项的数目为（该物品数+1）个 代码如下： #include<iostream>#include<algorithm>
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

原文链接： https://tecdat.cn/?p=37628 6月16日，小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞，这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示，公司准备量产，并计划今年四季度开启预售小鹏汇天分体式飞行汽车，探索分体式飞行汽车城际通勤。阅读原文，获取专题报告合集全文，解锁文末271份飞行汽车相关行业研究报告。 据悉，业内人士对飞行汽车行业
阅读更多...
hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
阅读更多...
软考系统规划与管理师考试证书含金量高吗？

软考系统规划与管理师考试证书含金量高吗？

2024年软考系统规划与管理师考试报名时间节点： 报名时间：2024年上半年软考将于3月中旬陆续开始报名 考试时间：上半年5月25日到28日，下半年11月9日到12日 分数线：所有科目成绩均须达到45分以上（包括45分）方可通过考试 成绩查询：可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间：预计在11月左右 证书领取时间：一般在考试成绩公布后3~4个月，各地领取时间有所不同
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2