01背包问题

有N件物品和一个容量为m的背包。第i件物品的费用是w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

二维

状态转移方程:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
循环:i:[i, n], j:[0, m]

降维

状态转移方程:dp[j] = max(dp[j], dp[j - w[i]] + v[i])
循环:i:[1, n], j:[m, w[i]]

完全背包问题

有N件物品和一个容量为C的背包。第i件物品的费用是w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和恰好等于背包容量,且价值总和最大。

二维

状态转移方程:dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+v[i])
循环:i:[i, n], j:[0, m]

降维

状态转移方程:dp[j] = max(dp[j], dp[j - w[i]] + v[i])
循环:i:[1, n], j:[w[i], m]