【算法刨析】完全背包

完全背包与01背包的区别

01背包对于一个物品只能选择一次，但是完全背包可以选择任意次； 

思路

和01背包类似，01背包我们只需要判断选或不选，完全背包也是如此，不同的是，对于这个物品我们在判断选后在增加一次选择的机会，直到不选，跳转至下一个物品即可；

一般代码：

 f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

第k次，不选的话就是它本身，选的话就是直接选择k次即可；

当然这个代码在数据稍微大一点的时候就会超出时间限制；

#include<iostream>
using namespace std;
const int N=1004;
int f[N][N];
int w[N],v[N];int main()
{int n,m;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;
}

优化思路

上面代码会超出时间限制是因为三层循环，下面我们来把第三层循环优化掉：

f[i][j]=max(f[i][j],f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,f[i-1][j-3*v]+3*w......f[i-1][j-k*v]+k*w)

f[i][j-v]=max(             f[i][j-v],f[i-1][j-2*v]+w,f[i-1][j-3*v]+2*w......f[i-1][j-k*v]+k*w)

f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,f[i-1][j-3*v]+3*w......f[i-1][j-k*v]+k*w 不就是f[i][j-v]+w

那么我们可以得到：f[i][j]=max(f[i][j],f[i-1][j-v]+w)

这样我们不就可以不用写第三层循环了吗？

直接用：

            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]);

优化代码：

#include<iostream>
using namespace std;
const int N=1004;
int f[N][N];
int w[N],v[N];int main()
{int n,m;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;
}

我们来看一下核心代码：

            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]);

还记得01背包的代码吗？
             f[i][j] = f[i - 1][j];

             if(j>=v[i])
             f[i][j]= max( f[i - 1][j],f[i - 1][j - v[i]] + w[i] );

是不是只有（红色标记）：

  f[i][j]= max( f[i - 1][j],f[i - 1][j - v[i]] + w[i] );不同

再次优化代码：

注意：

这里我的j的大小是从小到大开始的：

01背包中，f[i][j]= max( f[i - 1][j],f[i - 1][j - v[i]] + w[i] );对于f[j]就相当于f[i-1][j]的大小，如果从小到大遍历，那么f[i-1][j]的大小就会发现变化，那么优化后的代码就不满足我们所推导的公式，所以我们要从大到小；

类比于01背包，完全背包的公式， f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);对于这个公式如果从大到小就会改变f[i][j]的大小，不满足所推导的公式；

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e4;
int f[N];
int w[N],v[N];int main()
{int n,m;cin>>n>>m;for(int i=0;i<n;i++)cin>>v[i]>>w[i];for(int i=0;i<n;i++){for(int j=v[i];j<=m;j++){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m]<<endl;
}

以上就是全部内容！！