动态规划背包问题之完全背包详解

一、什么是完全背包问题

有n种物品每种物品的单件体积为v[i]价值为w[i]。现有一个容量为V的背包问如何选取物品放入背包使得背包内物品的总价值最大。其中每种物品都有无穷件。
完全背包和01背包的区别

1. 01背包在选择某一个物品时只有不选和选一次两种情况
2. 完全背包在选择某一个物品时可以不选也可以选一次选两次。。。选择次数没有上限只要背包能放下

二、例题分析

1. 题目

2. 分析

2.1 第一步确定状态变量函数

最大价值是物品数量i和背包容量j的函数。
设函数f[i][j]表示前i件物品放入容量为j的背包的最大价值。
最终的最大价值就是物品数量i从0增长到n背包容量j从0增长到m时的f[n][m]值。

2.2 第二步确定状态转移方程

状态变量f[i][j]表示前i件物品放入容量为j的背包的最大价值

当前容量为j我们要考虑第i件物品能否放入是否放入

1. 如果当前背包容量j<v[i],不能放入则f[i][j]=f[i-1][j]
2. 如果当前背包容量j>=v[i]能放入但是要比较代价
   2.1 如果第i件物品不放入背包则f[i][j]=f[i-1][j]
   2.2 如果第i件物品放入背包则f[i][j]=f[i][j-v[i]]+w[i]

对于前i件物品背包容量为j-v[i]时可能已经放入了第i件物品容量为j时还可以再放入第i件物品所以用f[i][j-v[i]]更新f[i][j]

状态转移方程

可以画图表示为

2.3 边界条件

对于01背包来说边界就是f[i][j]=0,即当i=0或者j=0时f[i][j]的值为0。

i=0时表示背包没有放入一个物品那么此时背包的最大价值无从谈起所以为0
j=0时表示背包的容量为0那么此时无法放入物品所以最大价值也为0

3. 过程表示

3.1 核心代码

    for(int i=1;i<=n;i++){//物品i
        for(int j=0;j<=m;j++)
            {
            if(j<v[i])
                f[i][j]=f[i-1][j];
             else
                f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
            }
     }
    cout<<f[n][m]<<endl;

3.2 手动计算

3.3 代码验证

3.4 完整代码

#include<iostream>
#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=1;j<=m;j++)
           {
               if(j<v[i])
                    f[i][j]=f[i-1][j];
                else
                    f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
           }
    cout<<f[n][m]<<endl;
    return 0;
}

3.5 优化

将二维表示优化成一维减少空间的使用用一维数组f[j]只记录一行数据让j值顺序循环顺序更新f[j]
优化后的代码

#include<iostream>
#include<algorithm>
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=1;j<=m;j++)
           {
               if(j<v[i])
                    f[j]=f[j];
                else
                    f[j]=max(f[j],f[j-v[i]]+w[i]);
           }
    cout<<f[m]<<endl;
    return 0;
}

因为j是顺序循环f[j-v[i]]会先于f[j]更新也就是说用新值f[j-v[i]]去更新f[j],相当于用第i行的f[j-v[i]]值更新f[j],所以正确。