题解 | #NC145 01背包 改进版#

import java.util.*;

public class Solution {
    // 定义物品类
    public class Goods {
        int v; // 体积
        int w; // 重量
    }
    
    public int knapsack (int V, int n, int[][] vw) {
        // 初始化物品列表
        List<Goods> list = new ArrayList<>();
        for (int i = 0; i < vw.length; i++) {
            Goods goods = new Goods();
            goods.v = vw[i][0];
            goods.w = vw[i][1];
            list.add(goods);
        }

        // 初始化动态规划矩阵
        int[][] dp = new int[n+1][V+1];
        // 将矩阵第一行和第一列填充为0，但默认值已为0.故略

        // 动态规划填充矩阵
        for (int i = 1; i <= n; i++) {
            // 获取当前待规划物品的信息
            Goods curGoods = list.get(i-1);
            for (int j = 1; j <= V; j++) {
                // 容量不足时
                if (j < curGoods.v) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    // 容量充足时，是否添加当前物品，视情况择优而定
                    dp[i][j] = Math.max(
                        dp[i-1][j],
                        dp[i-1][j-curGoods.v] + curGoods.w
                    );
                }
            }
        } // 矩阵填充完毕

        // 返回结果
        return dp[n][V];
    }
}