2023年8月1日发(作者：)

完全背包问题（详细解答）⾸先完全背包问题需要01背包问题做铺垫,如果读者01背包问题没有解决,⼀定要理解之后,在看完全背包问题,包括01背包的优化!这⾥是这⾥是好,我们开始完全背包!完全背包定义有N种物品和⼀个容量为V的背包，每种物品都有⽆限件可⽤。第i种物品的体积是v[i]，价值是val[i]。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。从定义中可以看出,与01背包的区别01背包最多只能拿⼀件物品,完全背包则不然,只要空间够多,⼀种物品我可以拿n件!01背包的状态转移⽅程为:dp(i,j)=max(dp(i-1,j),dp(i-1,j-v[i])+val[i])完全背包的状态转移⽅程:dp(i,j)=max(dp(i-1,j),dp(i,j-v)+val[i])我们可以看出,完全背包的动态转移⽅程max中第⼆项为i,⽽不是i-1。为什么呢?我们⽤01背包的思想去推导,完全背包的动态转移⽅程完全背包状态转移⽅程推导⾸先完全背包问题的动态转移⽅程可写为(w为val[i]简写)(v=v[i]简写)dp(i,j)=max(dp(i-1,j) , dp(i-1,j-v)+w , dp(i-1,j-2v)+2w , dp(i-1,j-3v)+3w,~~(以此类推到k) ,dp(i-1,j-k*v+kw))我简单解释⼀下上⾯的⽅程,其实就是利⽤01背包思想,要求⽆限个物品,实际上我最多能装V/v[i]个 (总体积除以的单个个体积),所以我从装0个,到装⼀个,2个,3个,k个这⾥⾯⼀定有其中⼀个,是能产⽣最⼤的价值!然后我们利⽤上述公式推导出"完全背包的状态转移⽅程"开始推导(时刻注意与这个⽅程的联系)dp(i,j)=max(dp(i-1,j) , dp(i-1,j-v)+w , dp(i-1,j-2v)+2w , dp(i-1,j-3v)+3w,~~(以此类推到k) ,dp(i-1,j-k*v+kw))推导开始还是利⽤01背包思想dp(i,j-v)=max( dp(i-1,j-v) , dp(i-1,j-2v)+w,dp(i-1,j-3v)+2w , dp(i-1,j-4v)+3w,~~~依次类推到k , dp(i-1,j-kv)+(k-1)w) )我们在这个⽅程两侧同时加上w,即可得到dp(i,j-v)+w=max( dp(i-1,j-v)+w , dp(i-1,j-2v)+2w,dp(i-1,j-3v)+3w , dp(i-1,j-4v)+4w,~~dp(i-1,j-kv)+kw)我们在回顾⼀下这个⽅程dp(i,j)=max(dp(i-1,j) , dp(i-1,j-v)+w , dp(i-1,j-2v)+2w , dp(i-1,j-3v)+3w,~~(以此类推到k) dp(i-1,j-k*v)+kw))可以发现dp(i,j-v)+w可以替代dp(i-1,j-v)+w , dp(i-1,j-2v)+2w , dp(i-1,j-3v)+3w,~~, dp(i-1,j-k*v)+kw所以我们得出完全背包的状态转移⽅程:dp(i,j)=max(dp(i-1,j),dp(i,j-v)+w)好了我们推导完成。然后我们看下代码:#include using namespace std;int N,V;int v[1010],val[1010];int dp[1010][1010];int main(){ scanf("%d%d",&N,&V); for(int i=1; i<=N; i++) { scanf("%d%d",&v[i],&val[i]); } for(int i=1; i<=N; i++) for(int j=0; j<=V; j++) { dp[i][j]=dp[i-1][j];//继承上⼀个背包 if(j>=v[i]) { //完全背包状态转移⽅程 dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+val[i]); } } printf("%d",dp[N][V]); return 0;}从宏观上理解,为什么会这样呢?我从代码的⾓度阐释⼀下这个问题!注意我们现在并没有对dp数组进⾏降维!我们的j是从0开始的,依次递增这个是完全背包的关键,也是与01背包本质的区别dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+val[i]);⾸先要满⾜完全背包的动态转移⽅程,就要先知道dp(i,j-v)的⼤⼩正好我们是从0开始的,并不是从后往前,也就是当求到dp(i,j)时dp(i,j-v),在前⾯已经求过所以我们可以应当理顺的求出dp(i,j)⽽不再是向01背包要考虑前i-1时候的状态!完全背包的优化然后我们根据01背包的优化原则对,完全背包进⾏优化!优化后的动态⽅程dp[j]=max(dp[j],dp[j-v]+w)代码(⾥⾯有⼀个点需要理解,我写在注释⾥了)#include using namespace std;int N,V;int v[1010],val[1010];int dp[1010];int main(){ scanf("%d%d",&N,&V); for(int i=1; i<=N; i++) { scanf("%d%d",&v[i],&val[i]); } for(int i=1; i<=N; i++) for(int j=0; j<=V; j++) { dp[j]=dp[j];//此时右边的dp[j]是上⼀层i-1的dp[j],然后赋值给了当前i的dp[i] if(j>=v[i]) { dp[j]=max(dp[j],dp[j-v[i]]+val[i]);//dp[j-v[i]],已经被算过 }

} printf("%d",dp[V]);//输出最⼤体积,即最优解 return 0;}感谢观看,希望⼤家多多⽀持⼀键三连!!嘻嘻~~

2023年8月1日发(作者：)

完全背包问题（详细解答）⾸先完全背包问题需要01背包问题做铺垫,如果读者01背包问题没有解决,⼀定要理解之后,在看完全背包问题,包括01背包的优化!这⾥是这⾥是好,我们开始完全背包!完全背包定义有N种物品和⼀个容量为V的背包，每种物品都有⽆限件可⽤。第i种物品的体积是v[i]，价值是val[i]。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。从定义中可以看出,与01背包的区别01背包最多只能拿⼀件物品,完全背包则不然,只要空间够多,⼀种物品我可以拿n件!01背包的状态转移⽅程为:dp(i,j)=max(dp(i-1,j),dp(i-1,j-v[i])+val[i])完全背包的状态转移⽅程:dp(i,j)=max(dp(i-1,j),dp(i,j-v)+val[i])我们可以看出,完全背包的动态转移⽅程max中第⼆项为i,⽽不是i-1。为什么呢?我们⽤01背包的思想去推导,完全背包的动态转移⽅程完全背包状态转移⽅程推导⾸先完全背包问题的动态转移⽅程可写为(w为val[i]简写)(v=v[i]简写)dp(i,j)=max(dp(i-1,j) , dp(i-1,j-v)+w , dp(i-1,j-2v)+2w , dp(i-1,j-3v)+3w,~~(以此类推到k) ,dp(i-1,j-k*v+kw))我简单解释⼀下上⾯的⽅程,其实就是利⽤01背包思想,要求⽆限个物品,实际上我最多能装V/v[i]个 (总体积除以的单个个体积),所以我从装0个,到装⼀个,2个,3个,k个这⾥⾯⼀定有其中⼀个,是能产⽣最⼤的价值!然后我们利⽤上述公式推导出"完全背包的状态转移⽅程"开始推导(时刻注意与这个⽅程的联系)dp(i,j)=max(dp(i-1,j) , dp(i-1,j-v)+w , dp(i-1,j-2v)+2w , dp(i-1,j-3v)+3w,~~(以此类推到k) ,dp(i-1,j-k*v+kw))推导开始还是利⽤01背包思想dp(i,j-v)=max( dp(i-1,j-v) , dp(i-1,j-2v)+w,dp(i-1,j-3v)+2w , dp(i-1,j-4v)+3w,~~~依次类推到k , dp(i-1,j-kv)+(k-1)w) )我们在这个⽅程两侧同时加上w,即可得到dp(i,j-v)+w=max( dp(i-1,j-v)+w , dp(i-1,j-2v)+2w,dp(i-1,j-3v)+3w , dp(i-1,j-4v)+4w,~~dp(i-1,j-kv)+kw)我们在回顾⼀下这个⽅程dp(i,j)=max(dp(i-1,j) , dp(i-1,j-v)+w , dp(i-1,j-2v)+2w , dp(i-1,j-3v)+3w,~~(以此类推到k) dp(i-1,j-k*v)+kw))可以发现dp(i,j-v)+w可以替代dp(i-1,j-v)+w , dp(i-1,j-2v)+2w , dp(i-1,j-3v)+3w,~~, dp(i-1,j-k*v)+kw所以我们得出完全背包的状态转移⽅程:dp(i,j)=max(dp(i-1,j),dp(i,j-v)+w)好了我们推导完成。然后我们看下代码:#include using namespace std;int N,V;int v[1010],val[1010];int dp[1010][1010];int main(){ scanf("%d%d",&N,&V); for(int i=1; i<=N; i++) { scanf("%d%d",&v[i],&val[i]); } for(int i=1; i<=N; i++) for(int j=0; j<=V; j++) { dp[i][j]=dp[i-1][j];//继承上⼀个背包 if(j>=v[i]) { //完全背包状态转移⽅程 dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+val[i]); } } printf("%d",dp[N][V]); return 0;}从宏观上理解,为什么会这样呢?我从代码的⾓度阐释⼀下这个问题!注意我们现在并没有对dp数组进⾏降维!我们的j是从0开始的,依次递增这个是完全背包的关键,也是与01背包本质的区别dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+val[i]);⾸先要满⾜完全背包的动态转移⽅程,就要先知道dp(i,j-v)的⼤⼩正好我们是从0开始的,并不是从后往前,也就是当求到dp(i,j)时dp(i,j-v),在前⾯已经求过所以我们可以应当理顺的求出dp(i,j)⽽不再是向01背包要考虑前i-1时候的状态!完全背包的优化然后我们根据01背包的优化原则对,完全背包进⾏优化!优化后的动态⽅程dp[j]=max(dp[j],dp[j-v]+w)代码(⾥⾯有⼀个点需要理解,我写在注释⾥了)#include using namespace std;int N,V;int v[1010],val[1010];int dp[1010];int main(){ scanf("%d%d",&N,&V); for(int i=1; i<=N; i++) { scanf("%d%d",&v[i],&val[i]); } for(int i=1; i<=N; i++) for(int j=0; j<=V; j++) { dp[j]=dp[j];//此时右边的dp[j]是上⼀层i-1的dp[j],然后赋值给了当前i的dp[i] if(j>=v[i]) { dp[j]=max(dp[j],dp[j-v[i]]+val[i]);//dp[j-v[i]],已经被算过 }

} printf("%d",dp[V]);//输出最⼤体积,即最优解 return 0;}感谢观看,希望⼤家多多⽀持⼀键三连!!嘻嘻~~