首页 > 试题广场 >

01背包

[编程题]01背包
  • 热度指数：27946 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
已知一个背包最多能容纳体积之和为v的物品

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

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

数据范围： ， ， ，

进阶 ：
示例1

输入

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

输出

4

说明

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

输入

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

输出

11

说明

两个物品体积之和等于背包能装的体积，所以两个物品都取是最优方案
算法知识视频讲解
开通博客
头像 LifelongCode
发表于 2021-01-15 18:01:15
0-1 背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？ 面对每个物品，我们只有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。 解决办法：声明一个大小为 展开全文
去ta的博客 赞 (18) 回复(2) 收起
头像 团子哒哒
发表于 2021-04-01 15:49:14
1.分析： dp[i][j]表示：对于前i个物品，当前背包的容量为j时，这种情况下可以装下的最大价值是dp[i][j]。如果你没有把这第i个物品装入背包，那么很显然，最大价值dp[i][j]应该等于dp[i-1][j]。你不装嘛，那就继承之前的结果。如果你把这第i个物品装入了背包，那么dp[i][j 展开全文
去ta的博客 赞 (13) 回复(2) 收起
头像 OfferCall！
发表于 2021-03-18 09:23:49
0-1背包 已知一个背包最多能容纳物体的体积为V 现有n个物品第i个物品的体积为v_i，第i个物品的重量为w_i 求当前背包最多能装多大重量的物品 解析 ​ dp[j]表示背包体积为j的情况下，能装的最大容量是多少。由于这是0-1背包问题，一个物品只能使用一次，所以采用一维的状态转移数组时，在 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 牛客92485225号
发表于 2022-01-02 20:24:34
dp表示的意思 是 n个物品 背包体积 V 能装的重量是dp[i][j] 这个容量的能装的最大重量 是取决 装不装第i-1 这个物品 不装 dp[i][j] = dp[i-1][j]; 装 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 佛说wh
发表于 2022-09-06 11:55:27
2022.0906算法第55题01背包 这道题也不容易想，但是竟然归为简单题， 我当时没想到需要和dp[i-1][j-vw[i-1][0]]离的那么远的值发生关系 1、状态矩阵建立了 2、初始值没弄ing错 3、状态转移方程没搞明白，已经把一个例子的状态矩阵写出来了 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 摸鱼学大师
发表于 2021-07-26 14:21:16
题目的主要信息： 背包体积固定为V，从所有物品中选择几件物品，加起来体积不超过V，使加起来质量最大。 所有数据大于0，无特殊情况 方法一：递归（超时） 递归是一种分治法，我们可以如下考虑： xix_ixi​为1或0，表示对于物品iii取或者不取，viv_ivi​表示物品iii的体积，wiw_i 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 团子哒哒
发表于 2021-04-12 11:28:09
题目：已知一个背包最多能容纳物体的体积为V，现有n个物品第i个物品的体积为wi， 第i个物品的重量为ci。且每种物品可以有无限个（0-1背包，一种物品只有一个）。求当前背包最多能装多大重量的物品。 我们根据0-1背包问题进行改造，因为0-1背包每次只考虑拿一次的最大值，而这里我们可以取 [当前背包 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 球球了给孩子一个offer吧
发表于 2021-07-26 16:56:21
描述已知一个背包最多能容纳物体的体积为V现有n个物品第i个物品的体积为, 第i个物品的重量为求当前背包最多能装多大重量的物品示例 输入：10,2,[[1,3],[10,4]]返回值：4说明：第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 牛客499819205号
发表于 2021-10-10 17:46:13
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算01背包问题的结果 * @param V int整型 背包的体积 * @param n int整型 物品的个 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 徐可可18739776523
发表于 2022-04-26 20:59:41
这里只放了答案，如果需要详细的步骤解析（有视频教程讲解），可以参考Python3使用动态规划处理01背包问题 另外我没有使用题目中自带的类名，而还是采用的打印的方式进行，关于解包变量可以参考：Python3使用exec函数将输入进来的结果的字符串的值解包成变量的值 题解1：二维列表 V, n, vw 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

动态规划
难度：
50条回答 8963浏览

热门推荐

通过挑战的用户

查看代码

相关试题

01背包

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号