完全背包问题基于01背包问题的变形

原题链接

基于y氏的dp方法链接，与本题分析非常相似

只是在区间划分，也就是区间计算中，有一点不一样

我们划分区间，是根据第i个物品选几个这样划分，又根据01背包的思路，我们能很轻松的写出每个状态的转移方程

f(i,j)=max(f(i-1,j),f(i-1,(j-v)+w),f(i-1,(j-2v)+2w),f(i-1,(j-3v)+3w),f(i-1,(j-nv)+nw))

在代码实现中，用k来枚举每个物品的个数，直到背包容量不够为止

未优化前的代码，这个代码会TLE，因为有三重循环

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N][N];


int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
        //k*v[i]<=j保证了背包的容量
            for(int k=0;k*v[i]<=j;k++)
            {
                f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

优化后的完全背包问题，可以优化到二维dp

我们根据上文已经知道了状态转移方程是根据下列式子来的

f(i,j)=max(f(i-1,j),f(i-1,(j-v)+w),f(i-1,(j-2v)+2w),f(i-1,(j-3v)+3w),f(i-1,(j-nv)+nw))

根据观察，我们能发现,f(i,j-v)等于

f(i,j-v)=max(f(i-1,j-v),f(i-1,(j-2v)+w),f(i-1,(j-3v)+2w),f(i-1,(j-4v)+3w),f(i-1,(j-nv)+(n-1)w))

我们发现，f(i,j)中的除f(i-1,j)这一项的剩下项能完全由f(i-j-v)表示，它们相差了一个w

这样我们完成了第一次优化，将三重循环简化为二重循环

接下来是数组空间优化
首先我们写出上一节推导出来的状态转移方程

f(i,j)=max(f(i-1,j),f(i,j-v)+w)

对比01背包问题,我们能发现，状态转移方程中，需要依赖当前已经遍历到的行数的数据，（因为有f(i,j-v)）

虽然，能够像类似01背包问题这样优化，但是在具体遍历滚动数组时，需要从前往后遍历，保证能用到当前行的数据

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int v[N],w[N],f[N];
int n,m;

int main()
{
    cin>>n>>m;
    for (int i = 1; i <= n; i ++ )cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=v[i];j<=m;j++)
        {
        //同样,max中的f[j]就代表上一行，也就是f(i-1,j)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}