动态规划学习笔记

待更新

背包动态规划

01背包

有\(N\)件物品和一个容量为\(V\)的背包。第\(i\)件物品的费用是\(c[i]\)，价值是\(w[i]\)。求解将哪些物品装入背包可使价值总和最大。

\(f[i][j]\)表示前\(i\)件物品恰放入一个容量为\(j\)的背包可以获得的最大价值，转移方程为

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

空间复杂度优化（压维）

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

完全背包

有\(N\)种物品和一个容量为\(V\)的背包，每种物品都有无限件可用。第\(i\)种物品的费用是\(c[i]\)，价值是\(w[i]\)。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

比01背包多一层枚举即可

for(int i = 0; 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]);
        }
    }
}

多重背包

有\(N\)种物品和一个容量为\(V\)的背包。第\(i\)种物品最多有\(a[i]\)件可用，每件费用是\(c[i]\)，价值是\(w[i]\)。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

用\(f[i][j]\)表示考虑前\(i\)种物品，一共用了\(j\)的费用的价值，则转移方程为

\[f[i][j] = max_{k <= a[i]}(f[i - 1][j - c[i] * k] + w[i] * k)\]

for(int i = 0; i < n; i++) {
    for(int j = 0; j <= m; j++) {
        for(int k = 0; k <= a[i]; k++) {
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i] + k * w[i]);
        }
    }
}

复杂度\(O(N * V * a[i])\)， 不满足要求

想优化！用二进制优化，转化为01背包问题