首页 > 试题广场 >

01背包

[编程题]01背包

热度指数：28841 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

已知一个背包最多能容纳体积之和为v的物品

现有 n 个物品，第 i 个物品的体积为 v_i , 重量为 w_i

求当前背包最多能装多大重量的物品?

数据范围： $1 \le v \le 1000$ ， $1 \le n \le 1000$ ， $1 \le v_i \le 1000$ ， $1 \le w_i \le 1000$

进阶： $O(n \cdot v)$

示例1

输入

10,2,[[1,3],[10,4]]

输出

说明

第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为4

示例2

输入

10,2,[[1,3],[9,8]]

输出

说明

两个物品体积之和等于背包能装的体积，所以两个物品都取是最优方案

算法知识视频讲解

Java

牛客944041779号

动龟5步：

1. 确定dp[i][j]含义，本题就是放置[i]物品在体积为j的背包里面。

2. 确定递推。遇到了物品[i]，那么需要考虑放不放[i]，如果放不下[i]，那么就取前面的一个那么dp[i][j]就是dp[i-1][j]。如果放得下[i]那么dp[i][j]就是dp[i-1][j-vw[i][0]]+vw[i][1]，就是上一个体积减去[i]的体积，就是[i-vw[i][0]]，然后还要加上[i]自身的价值/重量，那么就是+vw[i][1]，不过还需要和上一个比较一下，哪个价值大，所以总体上递推公式就是：dp[i][j] = max(dp[i-1][j],dp[i-1][j-vw[i][0]]+vw[i][1])

3. 确定初始化。绘制一个二维数组，需要初始化最上面那行，还有最左边那列。最上面那行就是(j=0;j<V;j++)如果j大于或者等于物品的重量，那么才能初始化放入背包物品的价值，否则就是0，因为放不进去，所以价值是0。然后初始化最左边那列，因为j=0所以没有重量，所以该列所有的价值都是0.

// define dp[i][j]
int[][] dp = new int[n][V+1];
// init
for(int i=0;i<n;i++){
    dp[i][0] = 0;//背包重量0放不了东西
}
for(int j = 0;j<=V;j++){
    // 如果j大于等于物品的重量才能初始化为物品的价值
    dp[0][j] = j>=vw[0][0]?vw[0][1]:0;
}

4. 确定遍历顺序。i为什么要从1开始，我也不知道，可能是如果i和j都从1开始那么就跳过一个步骤吧？？

//遍历
for(int i = 1;i<n;i++){
    for(int j = 0;j<=V;j++){
        if(j < vw[i][0]){// 放不了i，只能取前一个
            dp[i][j] = dp[i-1][j];
        }else{
            dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-vw[i][0]]+vw[i][1]);
        }
    }
}

5. 确定出口。就是dp最后一个元素还有对应的体积。就是

dp[n-1][V];

总体代码如下：

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
        // define dp[i][j]
        int[][] dp = new int[n][V+1];
        // init
        for(int i=0;i<n;i++){
            dp[i][0] = 0;//背包重量0放不了东西
        }
        for(int j = 0;j<=V;j++){
            // 如果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]){// 放不了i，只能取前一个
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-vw[i][0]]+vw[i][1]);
                }
            }
        }
        int r = dp[n-1][V];
        System.out.print(r);
        return r;
    }
}

发表于 2025-02-12 22:13:25 回复(0)

Java

在重庆的9527想飞翔

import java.util.*;

public class Solution {

public int knapsack (int V, int n, int[][] vw) {

// write code here

if (n == 1) {

if (vw[0][0] > V) return 0;

return vw[0][1];

}

int[][] dp = new int[n + 1][V + 1];

for (int i = n - 1; i >= 0; i--) {

for (int j = 0; j < V + 1; j++) {

int p1 = dp[i + 1][j];

int p2 = 0;

int flag = j - vw[i][0]<0 ? -1:dp[i+1][j-vw[i][0]];

if (flag != -1){

p2 = vw[i][1] + flag;

}

dp[i][j] = Math.max(p1, p2);

}

return dp[0][V];

}

发表于 2023-08-16 20:48:23 回复(0)

Java

giasodgo

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

试试递归，超时🌶

发表于 2022-08-13 17:44:15 回复(0)

Java

想润的我反对画饼

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
// dp[i][j]表示背包容量为i,要偷j件物品时能装的最大重量
int[][] dp = new int[V+1][n+1];
// 令第一列都为0;表示偷的0种时最多只能装0重量为0
for(int i = 0;i < dp.length;i++){
dp[i][0]= 0;
}
// 令第一行都为0,背包重量为0时最多只能偷0重量的物品
for(int i = 0;i<dp[0].length;i++){
dp[0][i] = 0;
}
int max = 0;
for(int i = 1;i < dp.length;i++){
for(int j = 1;j < dp[0].length;j++){
// vw[j-1][0]表示这个物品的重量,用当前容量-物品重量判断能不能装得下这个物品
int k = i - vw[j-1][0];
// k>=0说明能装得下否则说明装不下
if(k >= 0){
// dp[k][j-1]表示剩余容量最大得价值加下当前礼物的价值,dp[i][j-1]表示不拿当前物品以当前容量拿最多前几个物品
dp[i][j] = Math.max(dp[k][j-1]+vw[j-1][1],dp[i][j-1]);
}else{
dp[i][j] = dp[i][j-1];
}
}
}
return dp[V][n];
}

}

//题目思路来与动态规划DP0-1背包_哔哩哔哩_bilibili

发表于 2022-05-06 14:05:54 回复(0)

Java

奥因克

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

发表于 2021-11-28 01:21:37 回复(0)

Java

牛客507555376号

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 knapsack2(int V, int n, int[][] vw) {
        if (V <= 0 || n <= 0 || vw.length != n) {
            return -1;
        }
        int[][] w = new int[n + 1][V + 1];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 1; j <= V; ++j) {
                if (vw[i][0] <= j) {
                    w[i][j] = Math.max(w[i + 1][j - vw[i][0]] + vw[i][1], w[i + 1][j]);
                } else {
                    w[i][j] = w[i + 1][j];
                }
            }
        }
        return w[0][V];
    }

    public int knapsack(int V, int n, int[][] vw) {
        if (V <= 0 || n <= 0 || vw.length != n) {
            return -1;
        }
        int[] w = new int[V + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = V; j >= 1; --j) {
                if (vw[i][0] <= j) {
                    w[j] = Math.max(w[j - vw[i][0]] + vw[i][1], w[j]);
                }
            }
        }
        return w[V];
    }
}

发表于 2021-05-30 10:33:27 回复(0)

Java

阿尼亚瓦库瓦库

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

发表于 2021-05-14 17:13:40 回复(0)

Java

鲁班九号

https://cloud.tencent.com/developer/article/1574605

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

编辑于 2021-05-13 17:39:24 回复(0)

Java

惠灵顿靖

// dp[i][j]表示：对于前i个物品，当前背包的容量为j时，这种情况下可以装下的最大价值是dp[i][j]。
// 如果你没有把这第i个物品装入背包，那么很显然，最大价值dp[i][j]应该等于dp[i-1][j]。
// 你不装嘛，那就继承之前的结果。
// 如果你把这第i个物品装入了背包，那么dp[i][j]应该等于
// dp[i-1] [ j-vm[j-vm[i-1][0] ] + vm[i-1][1]。但还是需要和不装入进行大小比较，取价值最大的。
import java.util.*;
public class Solution {
public int knapsack (int V, int n, int[][] vw) {
       int v=V;
       int[][]dp=new int[n+1][v+1];
  for(int i = 1; i<=n;i++){
      for(int j = 1;j<=v;j++){
          if(j<vw[i-1][0]){//注意此处为i-1
              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]);
          }
      }
  }return dp[n][v];
       }
    }

编辑于 2021-04-02 14:21:52 回复(0)

Java

花落梦里

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

发表于 2021-03-30 16:56:19 回复(0)