补全动态规划解决背包问题的核心代码 int knapSack

// 0-1背包问题的动态规划实现
// 参数说明：
// W: 背包的最大容量
// wt[]: 物品重量数组，wt[i]表示第i个物品的重量
// val[]: 物品价值数组，val[i]表示第i个物品的价值
// n: 物品的数量
int knapSack(int W, int wt[], int val[], int n) {
    // 创建二维数组K用于存储子问题的解
    // K[i][w]表示：考虑前i个物品，背包容量为w时的最大价值
    int K[n + 1][W + 1];
 
    // 填充二维数组K（动态规划表）
    // i表示当前考虑的物品数量（从0到n）
    for (int i = 0; i <= n; i++) {
        // w表示当前背包的容量（从0到W）
        for (int w = 0; w <= W; w++) {
            // 基础情况：
            // 1. 当没有物品可选择（i=0）时，最大价值为0
            // 2. 当背包容量为0（w=0）时，无法装任何物品，最大价值为0
            if (i == 0 || w == 0) {
                K[i][w] = 0;
            }
            // 当第i个物品（索引为i-1）的重量小于等于当前背包容量w时
            // 可以选择放入或不放入该物品，取两种选择的最大值
            else if (wt[i - 1] <= w) {
                // 选择1：放入第i个物品
                // 价值 = 第i个物品的价值 + 剩余容量（w - 第i个物品重量）能装的最大价值
                // 剩余容量的最大价值由前i-1个物品计算（K[i-1][w - wt[i-1]]）
                
                // 选择2：不放入第i个物品
                // 价值 = 前i-1个物品在容量w下的最大价值（K[i-1][w]）
                
                // 取两种选择的最大值作为当前状态的最优解
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            }
            // 当第i个物品的重量大于当前背包容量w时
            // 无法放入该物品，当前最大价值等于前i-1个物品的最大价值
            else {
                K[i][w] = K[i - 1][w];
            }
        }
    }
    // 最终结果：考虑所有n个物品，背包容量为W时的最大价值
    return K[n][W];
}