完全背包问题详解

可以从0/1背包的角度来理解完全背包问题：

f(i,j)也就是状态表示集合的含义还是：所有只考虑前i个物品，且总体积不大于j的所有选法

0/1背包问题是从第i个物品选0还是选1来考虑，而完全背包是第i个物品选多少个来分。

【0】【1】【2】【3】...【k-1】【k】

第一个表示第i个物品选了0个，第二个表示第i个物品选了1个，以此类推

公式也同理，以此类推：

【0】--->f(i-1,j)
【k】--->f(i-1,j-kvi)+kwi

朴素算法

完全按照上面的思路来写即可，但现在过不了样例，报TLE错误

C++ 代码

#include<bits/stdc++.h>

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++)
            for(int k=0;k*v[i]<=j;k++)
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

    cout<<f[n][m]<<endl;
    return 0;
}

优化算法

对完全背包朴素算法进行优化：

f(i,j)=MAX(f[i-1,j],f[i-1,j-v]+w,...,f[i-1,j-kv]+kw)
f(i,j-v)=MAX(f[i-1,j-v],f[i-1,j-2v]+w,...,f[i-1,j-kv]+(k-1)w)

这里为什么两个最后的都是j-kv呢，因为第二个j-v了之后最多还能放k-1个v等于说下面的比上面的少放一个v所以最后一个还是j-kv。

//可以总结出fij不用和k项有关，只需要和两项有关即可。
f[i,j]=MAX(f[i-1,j],f[i,j-v]+w)

C++ 代码

#include<bits/stdc++.h>

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++)
           {
               f[i][j]=f[i-1][j];
               if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
           }


    cout<<f[n][m]<<endl;
    return 0;
}

循环数组算法

主要看细节，01背包是从i-1而完全背包要从i开始，所以从小到大对于完全背包来说是符合状态转移方程的。

C++代码

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int n,m;
int v[N],w[N];
int f[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=v[i];j<=m;j++)//j是从小到大枚举，j-vi小于j，所以是第i层的j-vi，同方程一致
           {
               f[j]=max(f[j],f[j-v[i]]+w[i]);
               // f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
           }

    cout<<f[m]<<endl;
    return 0;
}