当前位置:首页 > 动态规划 > 01背包 > 正文
SSOJ2405混合背包
255+

题目大意:n种物品放到一个载重量为m的背包,每种物品都限制了选的次数,可以是0次、1次、2次甚至更多次,背包最多能装多大价值的物品?

题目描述

一个旅行者有一个最多能装V公斤的背包,那么原则上有n件物品,他们的重量分别是W1,W2,…,Wn,它们的价值分别为C1,C2,…,Cn。有的物品只可以取一次(01背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。求解将哪些物品装入背包可以使这些物品的费用总和不超过背包容量,且价值总和最大。

输入

第1行:两个整数,M(背包容量,M<=200),N(物品数量,N<=30);

第2行至n+1行:每行三个整数Wi,Ci,Pi,前两个整数分别表示每个物品的重量,价值,第三个整数若为0,则说明此物品可以购买无数件;若为其他数字,则为此物品可购买的最多件数(Pi)。

输出

仅一行,一个数,表示最大总价值。

样例输入

10 3
2 1 0
3 3 1
4 5 4

样例输出

11

解题思路

如果是完全背包,那么从小到大枚举重量,让这种物品可以选无限次;如果是01背包,从大到小枚举重量,让这种物品只能够选一次;如果是可以选c次,把这种物品看成c种其他只能选一次的物品,进行c次01背包即可。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,

SSOJ2405混合背包:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter