首页 > 试题广场 >

完全背包

[编程题]完全背包
  • 热度指数：3155 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为v_i ,价值为w_i。

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？

数据范围：
示例1

输入

6,2,[[5,10],[3,1]]

输出

[10,2]
示例2

输入

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

输出

[20,0]

说明

无法恰好装满背包。
示例3

输入

13,6,[[13,189],[17,360],[19,870],[14,184],[6,298],[16,242]]

输出

[596,189]

说明

可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

动态规划
难度：
0条回答 2978浏览

热门推荐

通过挑战的用户

查看代码

相关试题

完全背包

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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