背包问题

01背包（物品只能使用一次）

朴素模板

int n, V;
int dp[N][N];
int v[N], w[N];

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

    for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= V; j ++){
            dp[i][j] = dp[i - 1][j]; // 不装第 i 个物品
            // 体积 j 够装 v[i]，看装与原来不装的区别
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    return dp[n][V];
}

一维优化

原本的 dp[i][j] 表示前 i 件物品、容量为 j 的背包所能得到的最大价值。在这个二维数组的动态规划中，当前状态 dp[i][j] 只依赖于上一层的状态 dp[i-1][j] 和 dp[i-1][j-v[i]]，因此我们可以使用滚动数组的思想，将二维 dp 压缩成一维数组 dp[j]。

滚动更新：因为每次只依赖上一行的状态，可以直接在同一个数组中更新当前行的状态。为了避免在更新当前状态时覆盖还未使用的旧状态，必须从后向前遍历容量 j，即从 V 到 v[i]，这样保证使用的是上一行的状态而不是本行已更新的状态。

int n, V;
int dp[N][N]; // 去掉一维
int v[N], w[N];

int solve(){
    for(int i = 1; i <= n; i ++){
        for(int j = V; j >= v[i]; j --){ // 从后往前覆盖
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    return dp[V];
}

方案寻找

vector<int> select;
void find(){
    // 回溯找出选择了哪些物品
    select.clear();
    int j = V;
    for (int i = n; i >= 1; i--){
        if (dp[i][j] != dp[i - 1][j]){ // 选了i
            select.push_back(i);
            j -= v[i]; // 剩余容量减少
        }
    }
}

完全背包（物品可使用无限次）

朴素模板（容易 TLE ）

int n, V;
int dp[N][N];
int v[N], w[N];

int solve(){
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= V; j ++){
            for(int k = 0; v[i] * k <= j; k ++){
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k*v[i]] + k*w[i]);
            }
        }
    }
    return dp[n][V];
}

k循环优化

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][j-v] = max( f[i-1][j-v], f[i-1][j-2v] + w, f[i-1][j-3v] + 2w, ...)

总结得出f[i][j] = max(f[i][j], f[i][j-v] + w)

int n, V;
int dp[N][N];
int v[N], w[N];

int solve(){
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= V; j ++){
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    }
    return dp[n][V];
}

进一步一维优化

k循环优化后

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

这部分代码与上部分01背包优化后的代码很相似，类比同样我们可以进一步一维优化

int n, V;
int dp[N];
int v[N], w[N];

int solve(){
    for(int i = 1; i <= n; i ++){
        for(int j = v[i]; j <= V; j ++){
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    return dp[V];
}

这里 j循环 是正序的，因为递推过程用到的 dp[i][j - v[i]] 是第 i 层且是 j 左侧的值

多重背包（物品可使用有限次）

朴素模板

与完全背包类似，k循环多一个条件k <= s[i]

int n, V;
int dp[N][N];
int v[N], w[N], s[N];

int solve(){
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= V; j ++){
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++){
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]*k] + w[i]*k);
            }
        }
    }
    return dp[n][V];
}

二进制优化

把每种物品(n个) 分别按照数量 $1,2,4,…,2^k$ 分组进行打包，若有物品剩余($n > 2^{k+1}-1$)，则将剩余物品打包为一组

然后采用 01背包 的方式，对每组物品采用选与不选（类似于二进制的每一位用 0 和 1 进行表示，可以按照一定选法表示出任何一个数，即任何一种物品数量选法）

const int N = max_n * log(max_s), M = V;

int n, V;
int dp[M];
int v[N], w[N];

int solve(){
    int cnt = 0; // 分组的组别
    for(int i = 1; i <= n; i ++){
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1; // 组别里的物品
        while(k <= s){
            cnt ++; // 组别次序
            v[cnt] = a * k; // 整组体积
            w[cnt] = b * k; // 整租价值
            s -= k; // 剩余物品个数
            k *= 2; // 组别里的个数 * 2（二进制）
        }
        if(s > 0){ // 剩余物品再分一组
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt; // 物品种类数变为物品组别数

    // 01背包
    for(int i = 1; i <= n; i ++){
        for(int j = V; j >= v[i]; j --){
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    return dp[V];
}

分组背包（多组物品，每组物品最多选一个）

整体代码与01背包类似，多加一层k循环来枚举每组的物品选择

v[i][j] / w[i][j]：第 i 组的第 j 个物品的 体积/价值

int n, V;
int dp[N];
int s[N], v[N][N], w[N][N];

int solve(){
    for(int i = 1; i <= n; i ++){
        for(int j = V; j >= 0; j --){
            for(int k = 1; k <= s[i]; k ++){
                if(v[i][k] <= j) dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
            }
        }
    }
    return dp[V];
}