完全背包定义

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

从定义中可以看出,与01背包的区别01背包最多只能拿一件物品,完全背包则不然,只要空间够多,一种物品我可以拿n件!

01背包的状态转移方程为:dp(i,j)=max(dp(i-1,j),dp(i-1,j-w[i])+v[i])
完全背包的状态转移方程:dp(i,j)=max(dp(i-1,j),dp(i,j-w)+v[i])

我们可以看出,完全背包的动态转移方程max中第二项为i,而不是i-1。

为什么呢?

我从代码的角度阐释一下这个问题!
注意我们现在并没有对dp数组进行降维!
我们的j是从0开始的,依次递增这个是完全背包的关键,也是与01背包本质的区别
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
首先要满足完全背包的动态转移方程,就要先知道dp(i,j-w)的大小
正好我们是从0开始的,并不是从后往前,也就是当求到dp(i,j)时
dp(i,j-w),在前面已经求过!!!
所以我们可以应当理顺的求出dp(i,j)而不再是向01背包要考虑前i-1时候的状态!

完全背包的优化

然后我们根据01背包的优化原则对,完全背包进行优化!
优化后的动态方程
dp[j]=max(dp[j],dp[j-w]+v)

#include<bits/stdc++.h>
using namespace std;
int dp[30005]; //dp[j] = 最大容量为j时的最大价值
int n,m;
int w[105],v[105];//w重量,v价值 
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=w[i];j<=m;j++)
        {    //dp[j] = dp[j] , dp[j-w[i]]+v[i]
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);  
        }
    }
    cout<<dp[m];
    return 0;
}