背包-完全背包
有 N 种物品，已知各件物品的重量和价值，第 i 种物品的重量为 wᵢ 和价值为 vᵢ 。(物品不可分割，要么取，要么不取，每种物品都可取任意件)。今有一背包，能装下每种物品的重量为 C ，问如何选若干件物品，总重量不超过 C，总价值达到最大。
【参考程序】
// 小牛编程
// 算法
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= C; j++) {
if (j - w[i] >= 0) {
for (int k = 0; k <= j / w[i]; k++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - k * w[i]] + k * v[i]);
}
}
}
}
// 或者
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= C; j++) {
dp[i][j] = dp[i - 1][j];
if (j - w[i] >= 0) {
for (int k = 0; k <= j / w[i]; k++) {
dp[i][j] = max(dp[i][j], dp[i][j - k * w[i]] + k * v[i]);
}
}
}
}
【滚动数组实现】
// 小牛编程
// 一维滚动数组（j是从小到大进行遍历的）
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= C; j++) {
if (j - w[i] >= 0) {
for (int k = 0; k <= j / w[i]; k++) {
dp[j] = max([j], dp[j - k * w[i]] + k * v[i]);
}
}
}
}