首页 > 试题广场 >

多重背包

[编程题]多重背包
  • 热度指数:2580 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
有一个体积为V的背包,有m种物品,每种物品有体积和价值,且数量一定。求背包能装下的最大价值。

输入描述:
第一行两个整数V和m。
接下来m行,每行3个整数,表示第i种物品的数量、体积和价值。
,个数、体积、价值不超过1000。


输出描述:
输出一个整数,表示背包能装下的最大价值。
示例1

输入

10 4
2 3 2
2 4 3
1 2 2
4 5 3

输出

8
头像 Huster水仙
发表于 2023-02-11 20:07:55
多重背包 每种物品有若干个,物品i的体积:w[i]、价值:v[i]、数量:amount 第i轮:dp[j]:前i个物品装进容量为j的背包所获得的最大价值 采用二进制 将同种物品组合成新的物品,化为0-1背包求解 #include<iostream> #include<string& 展开全文