题解 | #NC145 01背包#

import java.util.*;

// b站视频讲解地址：
// https://www.bilibili.com/video/BV1K4411X766/?spm_id_from=333.337.search-card.all.click&vd_source=46ab2667c40e3a397d8db3c4f6ceacf9
public class Solution {
    public int knapsack (int V, int n, int[][] vw) {
        // 初始化
        int[][] dp = new int[n+1][V+1];
        // 将矩阵第一行和第一列填充为0，但默认值已为0，故略
        // vw[i-1]: 当前行的物品信息
        // vw[i-1][0]: 物品体积 vw[i-1][1]: 物品重量

        // 动态规划填充矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                // 容量不足时
                if (j < vw[i-1][0]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    // 能装，但装不装看情况
                    // 不装则dp[i][j] = dp[i-1][j]
                    // 装则dp[i][j] = dp[i-1][j-vw[i-1][0]]+vw[i-1][1]
                    dp[i][j] = Math.max(
                        dp[i][j] = dp[i-1][j],
                        dp[i-1][j-vw[i-1][0]]+vw[i-1][1]
                    );
                }
            }
        } // 动态规划结束

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