大家好，又见面了，我是你们的朋友全栈君。
首先完全背包问题需要01背包问题做铺垫,如果读者01背包问题没有解决,一定要理解之后,在看完全背包问题,包括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 <iostream>
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 <iostream>
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;
}
感谢观看,希望大家多多支持一键三连!!
嘻嘻~~
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/147830.html原文链接：https://javaforall.net
