一共 20 个种类的物品，每个种类有 10 件，每件都有价格，运费，评分 （价格在 1-20 之间，运费在 2-5 之间）
问，每个总类最多拿一件物品，要求在价格+运费<=50 的情况下 使得评分之和最高
This topic created in 2496 days ago, the information mentioned may be changed or developed.
 |
1
newtype0092 Jul 25, 2019
搜《背包九讲》，一次解决所有相关问题。你这个应该属于里面的“分组背包”问题。
|
 |
2
litmxs Jul 25, 2019 via Android
背包
|
 |
3
jmc891205 Jul 25, 2019 via iPhone
每种最多只能拿 1 件的话
每种有 10 件这个条件好像没啥用 |
 |
4
Oz2011 OP @newtype0092 可问题是，完全有可能不从某组中拿东西啊
|
 |
5
DaCong Jul 26, 2019  1
同 1 楼，这个问题已经被《背包九讲》讨论过，这里给出链接 https://github.com/tianyicui/pack/blob/master/V2.pdf
请看其中的分组背包一节。 你说的“完全有可能不从某组中拿东西啊”，而《背包九讲》中分组背包一节中提到“这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。”可见你的问题已经被文档所涵盖。 |
Select Language