完全背包问题(详细解答)

全栈程序员-站长 • 2022年6月15日上午9:16 • 未分类 • 阅读 32

大家好，又见面了，我是你们的朋友全栈君。

首先完全背包问题需要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;
}