菜鸡求助

P1064 [NOIP2006 提高组] 金明的预算方案

_LanFeng_ @ 2019-07-05 20:41:23

2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5

各位大佬,我的思路是讨论4种情况后转换为01背包,以上数据转换后就会变成12个物品,如下(左边是价钱,右边是价值)

500 500
800 2000
900 2500
1200 4000
400 1600
200 1000
700 3000
600 2200
1100 4200
400 1600
320 640
410 1230

很明显,01背包跑出来是8200,但是答案却是7430,说明我理解错题意了,但我翻遍了讨论和题解也没发现哪错了。。那么这组数据到底应该怎么分呢?麻烦各位大神了


by robbie @ 2019-07-05 21:40:23

不客气鸭~一起进步


上一页 |