s****g
发帖数: 43 | 1 小朋友去露营。老师发了一个要带的东西的单子。运动器材店的东西是打包卖的，每包
东西的组合不同，价格也不同。求以最少的钱把要的东西都买下来。
有点像换硬币最少方式(or knapsack variation?)，可是没能找出动态公式来。 | l*****a
发帖数: 14598 | 2 这样做是否可以？
你需要item1,item2..itemn
人家有 package1,package2,package3... packagek(sort by total price)
item1 is in p1,p3,p4...
item2 is in p1,p5,p7
...
...
itemn is in p*,p*,P*
则 每个package list首项 一定包含item1..itemn 记录一个cost
然后移动package number最小的那个list的index,找到一个新的组合，包含所有。以此
类推
注意p1+p2>p3 所以第一项不见得是最小的，需要找到所有可能
【在 s****g 的大作中提到】
: 小朋友去露营。老师发了一个要带的东西的单子。运动器材店的东西是打包卖的，每包
: 东西的组合不同，价格也不同。求以最少的钱把要的东西都买下来。
: 有点像换硬币最少方式(or knapsack variation?)，可是没能找出动态公式来。
| q****m
发帖数: 177 | 3 simplex?
【在 s****g 的大作中提到】
: 小朋友去露营。老师发了一个要带的东西的单子。运动器材店的东西是打包卖的，每包
: 东西的组合不同，价格也不同。求以最少的钱把要的东西都买下来。
: 有点像换硬币最少方式(or knapsack variation?)，可是没能找出动态公式来。
| g***x
发帖数: 45 | 4 这不是NP么？莫非我理解错了
【在 s****g 的大作中提到】
: 小朋友去露营。老师发了一个要带的东西的单子。运动器材店的东西是打包卖的，每包
: 东西的组合不同，价格也不同。求以最少的钱把要的东西都买下来。
: 有点像换硬币最少方式(or knapsack variation?)，可是没能找出动态公式来。
| i**********a
发帖数: 149 | 5 典型的set covering问题啊
【在 s****g 的大作中提到】
: 小朋友去露营。老师发了一个要带的东西的单子。运动器材店的东西是打包卖的，每包
: 东西的组合不同，价格也不同。求以最少的钱把要的东西都买下来。
: 有点像换硬币最少方式(or knapsack variation?)，可是没能找出动态公式来。
|
|
