背包类型分类

01背包

01背包是整个背包问题基础。

dp思路：

表达

dp[i][j] 代表 前i个物品，体积最大不超过j的最大权重选法集合。

表达式：

权重最大

转换公式

dp[i][j] = max(dp[ i-1 ][ j ],dp[ i-1 ][ j-v[i] +w[i]) # dp[i-1][j] 不选第i个物品 dp[i-1][j-v[i]] 选择第i个物品

代码

// 二维数组写法
// for(int i=1;i<=n;i++)
//     for(int j=1;j<=m;j++)
//         f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
// 一维数组写法

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1000 + 7;
int f[N],v[N],w[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=m;j>=v[i];j--){
            f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    cout << f[m] << endl;
    return 0;
}

完全背包

完全背包和01背包的区别是每个物品可以选择多种情况，0,1,2,3 … m/v[i] 个。所以要进行数学转换。

f[i][j] = max(f[i-1][j] , f[i-1][j-1v[i]] + 1 * w[i] , f[i-1][j-1 * v[i]] + 1 * w[i] , f[i-1][j-2 * v[i]] + 2 * w[i] … f[i-1][j-a * v[i]] + a * w[i]);
两边减去 v[i] 加上 w[i]
f[i][j-v[i]] + w[i] = max(f[i-1][j-1v[i]] + 1 * w[i] , f[i-1][j-1 * v[i]] + 1 * w[i] , f[i-1][j-2 * v[i]] + 2 * w[i] … f[i-1][j-a * v[i]] + a * w[i]);

==>

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

dp思路：

表达

dp[i][j] 代表 前i个物品，体积最大不超过j的最大权重选法集合。

表达式：

权重最大

转换公式

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

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000 + 7;
int f[N],v[N],w[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++)
            f[j] = max(f[j],f[j-v[i]]+w[i]);     
    cout << f[m] << endl;
    return 0;
}

note:
完全背包第二层遍历 关系到 i,i-1 所以 一维压缩写法必须是递增 大于j的是 i-1 维度的。

多重背包

多重背包每个物品有s[i]个，则有最多s+1种情况，0，1，2，3… s 种情况。
f[i][j] = max(f[i-1][j] , f[i-1][j-1 * v[i]] + 1 * w[i] , f[i-1][j-1 * v[i]] + 1 * w[i] , f[i-1][j-2 * v[i]] + 2 * w[i] … f[i-1][j-s[i] * v[i]] + s[i] * w[i]); (s` * v[i] < m);

dp思路：

表达

dp[i][j] 代表 前i个物品，体积最大不超过j的最大权重选法集合。

表达式：

权重最大

转换公式

f[i][j] = max(f[i-1][j] , f[i-1][j-1 * v[i]] + 1 * w[i] , f[i-1][j-1 * v[i]] + 1 * w[i] , f[i-1][j-2 * v[i]] + 2 * w[i] … f[i-1][j-s[i] * v[i]] + s[i] * w[i]); (s` * v[i] < m);

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 107;
int v[N],w[N],s[N],f[N][N];
int n,m;

int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> v[i] >> w [i] >> s[i];
    for(int i=1;i<=n;i++) 
        for(int j=0;j<=m;j++)
            for(int k=0;k<=s[i]&&j>=k*v[i];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;
}

note:
也可以转换为01背包问题， 第i组转换成s[i]组个物品，这样 i * j * s -> (i * s) * j;