这是一个创建于 1955 天前的主题，其中的信息可能已经有所发展或是发生改变。
一共 20 个种类的物品，每个种类有 10 件，每件都有价格，运费，评分 （价格在 1-20 之间，运费在 2-5 之间）
问，每个总类最多拿一件物品，要求在价格+运费<=50 的情况下 使得评分之和最高
 |
1
newtype0092 2019-07-25 20:42:56 +08:00
搜《背包九讲》，一次解决所有相关问题。你这个应该属于里面的“分组背包”问题。
|
 |
2
litmxs 2019-07-25 20:43:52 +08:00 via Android
背包
|
 |
3
jmc891205 2019-07-25 20:46:04 +08:00 via iPhone
每种最多只能拿 1 件的话
每种有 10 件这个条件好像没啥用 |
 |
4
Oz2011 OP @newtype0092 可问题是，完全有可能不从某组中拿东西啊
|
 |
5
DaCong 2019-07-26 21:06:17 +08:00  1
同 1 楼，这个问题已经被《背包九讲》讨论过，这里给出链接 https://github.com/tianyicui/pack/blob/master/V2.pdf
请看其中的分组背包一节。 你说的“完全有可能不从某组中拿东西啊”，而《背包九讲》中分组背包一节中提到“这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。”可见你的问题已经被文档所涵盖。 |
Select Language