背包-多重背包
有 N 种物品和一个容量为 C 的背包。第 i 种物品最多有 p[i] 件可用，每件重量是 w[i]，价值是 v[i]。
求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且总价值最大。
多重背包就是把完全背包的数量 k 规定在 p[i] 的范围内。
【参考程序】
// 小牛编程
// 算法
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 <= p[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 <= p[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 <= p[i]; k++) {
dp[j] = max([j], dp[j - k * w[i]] + k * v[i]);
}
}
}
}