有 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]);
            }
        }
    }
}