0-1背包

218. 01背包问题

322. 零钱兑换

518. 零钱兑换 II

面试题 08.11. 硬币

剑指 Offer II 103. 最少的硬币数目

剑指 Offer II 104. 排列的数目

背包容量为$W$，物品数量为$n$，每个物品的重量为$w{i}$，价值为$v{i}$。

每个物品都只有一件，求背包能装下的最大价值？

状态定义

$dp[i][j]$：从前$i$​个物品中选出总重量不超过$j$的最大价值。

状态转移方程

$dp[i][j]= \begin{cases}
dp[i - 1][j], \ j=w[i]
\end{cases}$

最终答案为：$dp[n][W]$

int[][] dp = new int[n + 1][W + 1];
int[] w = new int[n];
int[] v = new int[n];

// dp
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
        // 背包容量小于当前物品重量
        if (j < w[i - 1]) {
            dp[i][j] = dp[i - 1][j];
        }
        // 背包容量可以装的下当前物品
        else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i -1][j - w[i - 1]] + v[i -1]);
        }
    }
}
// ans = dp[n][W];

空间优化

可以发现，计算当前行状态时，只与上一行的状态有关，所以可以用滚动数组来优化空间。

int[] dp = new int[W + 1];
int[] w = new int[n];
int[] v = new int[n];

// dp
for (int i = 1; i <= n; i++) {
    int[] temp = new int[W + 1];
    for (int j = 0; j <= W; j++) {
        if (j < w[i - 1]) {
            temp[j] = dp[j];
        } else {
            temp[j] = Math.max(dp[j], d[j - w[i - 1]] + v[i - 1]); 
        }
    }
    dp = temp;
}

// ans = dp[W]