题解 | 01背包

class Solution 
{
    // 定义dp数组：dp[j]表示背包承重为j时能获得的最大价值
    // 初始化全为0（未放任何物品时，价值为0）
    int dp[1010] = {0}; 
public:
    // 函数参数：V（背包最大承重）、n（物品数量）、vw（物品的重量和价值数组）
    int knapsack(int V, int n, vector<vector<int> >& vw) 
    {
        // 第一层循环：遍历每件物品（0-1背包中每件物品只能选一次）
        for(int i = 0; i < n; i++)
        {
            // 第二层循环：从背包最大承重V开始，倒序遍历到当前物品的重量vw[i][0]
            for(int j = V; j >= vw[i][0]; j--)
            {
                // 状态转移方程：
                // 对于承重j，有两种选择：不选第i件物品（价值为dp[j]），或选第i件物品（价值为dp[j - 物品重量] + 物品价值）
                // 取两种选择的最大值，更新dp[j]
                dp[j] = max(dp[j], dp[j - vw[i][0]] + vw[i][1]);
            }
        }

        // 返回背包承重为V时的最大价值
        return dp[V];
    }
};