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

    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];
    }

       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];
    }
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算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];
    }
};

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 计算01背包问题的结果
 * @param V int整型 背包的体积
 * @param n int整型 物品的个数
 * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
 * @param vwRowLen int vw数组行数
 * @param vwColLen int* vw数组列数
 * @return int整型
 */
int knapsack(int V, int n, int** vw, int vwRowLen, int* vwColLen ) {
    // write code here
    //(*returnColumnSizes)[count]=3;
    int **dp=(int **)malloc((n+1)*sizeof(int*));
    vwRowLen=n;
    (*vwColLen)=2;
    for(int i=0;i<=n;i++){
        dp[i]=(int *)calloc(V+1,sizeof(int));
        
    }
    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-vw[i-1][0]]+vw[i-1][1])>dp[i-1][j]?(dp[i-1][j-vw[i-1][0]]+vw[i-1][1]):dp[i-1][j];
            }
        }
        
    }
    return dp[n][V];
    }

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # V 体积 。 n :物品个数 
        # 就是填表的过程。然后就出来结果了。
        # 列 是 体积的大小 
        # 行 是 物品的个数 + 1
        # 第一行 第一列 都是 0 。
        # 第 dp[row][col] 代表：在 可以装 col 的情况下，选择 前row个物品的最优解。
        # dp = [[0] * (V + 1)] * (n+1)  我这个dp数组生成的有问题,, 我。。我服了啊。用下面的就可以。打印出来长一模一样啊。
        dp = [[0 for i in range(V+1)] for j in range(n+1)]
        for row in range(1, n+1): 
            # 从左到右填表
            for col in range(1, V + 1):
                # 从上到下填表 
                # 到第row 个的时候咋选择
                # 首先看当前物品的重量是否超过当前体积。如果超过了。就填正上面的解。
                if vw[row-1][0] > col:
                    # col 是当前体积。 vw[row-1][0] 是代表到第row-1个物品。
                    # 说明不能装当前物品。当前局部最优解就是 dp[row-1][cow].
                    dp[row][col] = dp[row-1][col]
                else:
                    # 当前物品的重量小于当前的体积
                    # 这个时候有俩种情况，装当前的物品还是不装当前的物品
                    # 然后比较俩种情况，谁好选择谁

                    # 第一种情况：装当前物品，那么剩余的体积就是 col - 当前体重。
                    data_rest = col - vw[row-1][0] # 需要计算在data_rest体重的情况下，前 row-1个的最优解
                    data_1  = vw[row-1][1] + dp[row-1][data_rest]

                    # 第二种情况：不装当前物品
                    data_2  = dp[row-1][col] # 就正上方的数据

                    # 比较data_1 data_2 
                    dp[row][col] = max(data_1, data_2)
        
        return dp[-1][-1]

为啥生成dp数组打印出来一模一样，一个可以，一个不行。服了。。

class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        l=[[0 for i in range(V+1)] for j in range(n+1)]

        for i in range(1,n+1):
            for j in range(1,V+1):
                if vw[i-1][0]>j:
                    l[i][j]=l[i-1][j]
                else:
                    l[i][j]=max(l[i-1][j],l[i-1][j-vw[i-1][0]]+vw[i-1][1])
        return l[n][V]

public class Solution {
    public int knapsack (int V, int n, int[][] vw) {
        return process(vw,0,0,0,V,n);
    }
    public int process(int[][] vw,int i,int alreadyW,int alreadyV,int V,int n) {
    	if(alreadyV>V) {
    		return 0;
    	}
    	if(i==n) {
    		return alreadyW;
    	}
    	return Math.max(process(vw,i+1,alreadyW,alreadyV,V,n),
    			process(vw,i+1,alreadyW+vw[i][1],alreadyV+vw[i][0],V,n));
    }
}