当前位置:首页 > 动态规划 > 01背包 > 正文
SSOJ2401分组背包
1362+

题目大意:n件物品,各有重量价值分类,每种只能选一件,背包容量是m,最大能装多大价值?

题目描述

一个旅行者有一个最多能装V公斤的背包,现在有n件物品,它们的重量分别是W1,W2,…Wn,它们的价值分别为C1,C2…,Cn。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

输入

第1行:三个整数,V(背包容量,V<=200),N(物品数量,N<=30)和T(最大组号,T<=10);

第2行至N+1行:每行三个整数Wi,Ci,P,表示每个物品的重量、价值、所属组号。

输出

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

样例输入

10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3

样例输出

20

解题思路

关键是如何保证每一组物品只选一件?把一组物品看做是一件物品,一组一组枚举,让后保证每组选一件,从大到小进行01背包——对于每一个容量,枚举该组物品的背包,如果装进去价值更大就更新。为什么这样可以保证一组只选一件?因为在计算f[m]的时候,f[m-体积]还是之前的,这一组的还没算出来,更新f[m]的时候,只是选了对这组背包中最有利的一个背包而已。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,

SSOJ2401分组背包:等您坐沙发呢!

发表评论

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

快捷键:Ctrl+Enter