0-1背包

0-1背包

已知一个背包最多能容纳物体的体积为V

现有n个物品第i个物品的体积为v_i，第i个物品的重量为w_i

求当前背包最多能装多大重量的物品

解析

​ dp[j]表示背包体积为j的情况下，能装的最大容量是多少。由于这是0-1背包问题，一个物品只能使用一次，所以采用一维的状态转移数组时，在内循环遍历背包容量时，要采用逆序，避免同一件物品被重复使用。

public int knapsack (int V, int n, int[][] vw) {
    // write code here

    int[] dp = new int[V + 1];
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = V; j >= vw[i][0]; j--) {

            if (j >= vw[i][0]){

                dp[j] = Math.max(dp[j],dp[j - vw[i][0]] + vw[i][1]);
            }
        }
    }
    return dp[V];
}