01背包

class Solution:
    def knapsack(self , V , n , vw ):
        # write code here
        '''dp是一个矩阵，行是考虑的物品数，分别是0，1，2； 列是背包的可用空间分别是0，1，2，。。。，10；
        而对应位置的值就是给定条件下可以放的最大重量'''
        dp = [[0 for j in range(V+1)] for i in range(n+1)]
        '''这里给vw的index0插入了一个【0，0】是为了之后代码遍历方便点，这样index0 表示考虑0件物品'''
        vw.insert(0,[0,0])
        '''对每一行进行遍历，注意，行的index就是代表考虑最近的index件物品'''
        for row in range(1,n+1):
            for col in range(V+1):
                if vw[row][0]> col:
                    dp[row][col] = dp[row-1][col]
                else:
                    dp[row][col] = max(dp[row-1][col], dp[row-1][col-vw[row][0]] + vw[row][1])
        return dp[n][V]

class Solution:
    def knapsack(self , V , n , vw ):
        res=[0 for i in range(V+1)]
        for i in range(1,n+1,1):
            for j in range(V,0,-1):
                if j>=vw[i-1][0]:
                    res[j]=max(res[j],res[j-vw[i-1][0]]+vw[i-1][1])
        result=res[V]
        return result

       if (V == 0 || n == 0 || vw.empty()) {
            return 0;
        }

        vector<vector<int>> dp(n + 1, vector<int>(V + 1, 0));
        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] = max(dp[i-1][j], dp[i-1][j - vw[i-1][0]] + vw[i-1][1]);
                }
            }
        }

        return dp[n][V];

如果你没有把这第i个物品装入背包，那么很显然，最大价值dp[i][j]应该等于dp[i-1][j]。你不装嘛，那就继承之前的结果。

  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] = Math.max(dp[i-1][j],dp[i-1][j-vw[i-1][0]]+vw[i-1][1]);
          }
      }
  }

3、考虑空间的优化

 for(int i = 1; i<=n;i++){
     for(int j = V;j>0;j--){
         if(j<vw[i-1][0]){
             dp[j] = dp[j];
         }else{
             dp[j] = Math.max(dp[j],dp[j-vw[i-1][0]]+vw[i-1][1]);
         }
     }
 }

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        // 备注 1 参考文章 https://cloud.tencent.com/developer/article/1574605
        // 备注 2 vw 的索引范围, vw[0,199][0,1]
        // 数组范围 +1, 简化代码, 比如不用 return dp[n-1][V-1], 且由于循环从 1 开始后续的 dp[i-1][j] 不用担心当 i==0 的时候 dp[-1][j] 会数组越界
        int dp[][] = new int[n+1][V+1];
        // 背包可容纳前 i (数量区间为[0,i]) 物品数量的最大(重量/价值)
        for(int i=1; i<=n; i++){
            // 背包最大可容纳体积为 j
            for(int j=1; j<=V; j++){
                // 先获取背包可容纳前 i-1 (数量区间为[0,i-1]) 物品数量的最大(重量/价值)
                int oldMax = dp[i-1][j];
                // 新的物品的体积
                int iV = vw[i-1][0];
                // 新的物品的(重量/价值)
                int iW = vw[i-1][1];
                // 如果新的物品的体积可以被背包容纳
                if(j >= iV){
                    // 先计算好当体积为 j(当前背包最大可容纳体积) - iV(新的物品的体积) 时 背包可容纳前 i-1 (数量区间为[0,i-1]) 物品数量的最大(重量/价值)(已经在之前的步骤中计算好, 因为 0 < iV <= j, 所以 dp[i-1][j-iV] 已知)
                    // 然后 + iW(新的物品的(重量/价值))
                    // 即可得到 背包可容纳前 i (数量区间为[0,i]) 物品数量的最大(重量/价值)
                    int value = dp[i-1][j-iV] + iW;
                    // 取最大值
                    if(value > oldMax){
                       dp[i][j] = value; 
                    }else{
                       // 说明性价比不高, 之前存在(重量/价值)较大且体积较小的物品
                       dp[i][j] = oldMax;
                    }
                }else{
                    // 新的物品体积无法被背包容纳, 则背包可容纳的前i个物品数量的最大(重量/价值)等同于前i-1, 直接赋值
                    dp[i][j] = oldMax;
                }
            } 
        }
        return dp[n][V];
    }
}

    public int knapsack (int V, int n, int[][] vw) {
       int[]dp=new int[V+1];//dp[i]背包体积为i的最多容纳的重量
       for(int i=0;i<n;i++){//判断第I个物品要不要加入
           for(int j=V;j>0;j--){
               if(vw[i][0]<=j){//第i个可以加入
                   dp[j]=Math.max(dp[j],dp[j-vw[i][0]]+vw[i][1]);//加入之后重量的变化
               }
           }
       }
        return dp[V];
    }

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int knapsack(int V, int n, vector<vector<int>>& vw) {
    // dp[i][j]表示前i个物品，背包容量为j时的最大价值
    vector<vector<int>> dp(n, vector<int>(V + 1, 0));
    
    // 初始化
    for (int j = 0; j <= V; j++) {
        dp[0][j] = (j >= vw[0][0]) ? vw[0][1] : 0;
    }
    
    // 动态规划
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= V; j++) {
            if (j < vw[i][0]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - vw[i][0]] + vw[i][1]);
            }
        }
    }
    
    cout << dp[n-1][V] << endl;
    return dp[n-1][V];
}

int main() {
    // 示例测试
    int V = 10;
    int n = 5;
    vector<vector<int>> vw = {{2,6}, {2,3}, {6,5}, {5,4}, {4,6}};
    knapsack(V, n, vw);
    return 0;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算01背包问题的结果
 * @param V int整型 背包的体积
 * @param n int整型 物品的个数
 * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
 * @return int整型
 */
function knapsack(V, n, vw) {
    // write code here
    const val = Array.from({ length: V + 1 }).map(() =>
        new Array(n + 1).fill(0)
    );

    Array.from({ length: V + 1 }).forEach((_, volumn) => {
        Array.from({ length: n + 1 }).forEach((_, count) => {
            if (!volumn || !count) return;
            const [objVolumn, objWeight] = vw[count - 1];
            if (volumn - objVolumn >= 0) {
                val[volumn][count] = Math.max(
                    val[volumn][count - 1],
                    val[volumn - objVolumn][count - 1] + objWeight
                );
            } else {
                val[volumn][count] = val[volumn][count - 1];
            }
        });
    });

    return val[V][n];
}
module.exports = {
    knapsack: knapsack,
};

class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # dp[i][j]代表容量为j时在第i个物品能装的最大重量
        # 状态转移方程
        # 两种情况：
        # 1）当前物品的体积超过j,那么无法放入该物品，dp[i][j] = dp[i-1][j]
        # 2）当前物品的体积不超过j,有两种选择，取两者的较大值：
        #     不放该物品，能装的最大重量为dp[i-1][j]
        #     放入该物品，能装的最大重量为dp[i-1][j-cur_v] + cur_w
        # 观察数组可知，当体积为0或物品为0时，最大重量为0，因此第0行和第0列为0
        # 初始化二维数组
        dp = [[0]*(V+1) for i in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, V+1):
                # 当前物品的体积
                cur_v = vw[i-1][0]
                # 当前物品的重量
                cur_w = vw[i-1][1]
                if cur_v > j:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-cur_v] + cur_w)
        return dp[-1][-1]

class Solution {
public:
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        // write code here
        int dp[1010];
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<n;i++)
            for(int j=V;j>=vw[i][0];j--)
             dp[j] = max(dp[j],dp[j-vw[i][0]] + vw[i][1]);

        return dp[V];
    }
};