c********t
发帖数: 5706 | 1 从n个无重复正整数的数组里选m个数，要求这m个数的总和是<=S的最大解。
比如 从{1,3,9,15} 选 m=2个,<=13, 答案就是{3,9}。如果<=10,答案就是{1,9} |
n*****s
发帖数: 6495 | 2 knapsack吧
2个dependency变成1个就行 O(mS) |
c********t
发帖数: 5706 | 3 开始套不进knapsack去，因为把限定的value想当做weight的限制。
后来发现这个限制应该在benefit value上，只要在knapsack中间，比较一下总value是
不是超过limit就行了
【在 n*****s 的大作中提到】
: knapsack吧
: 2个dependency变成1个就行 O(mS)
|
n*****s
发帖数: 6495 | 4
普通的背包是P(n, K)depends on P(n-1, K)或者P(n-1, K-Ki)
这个应该只要P(n-1, K-Ki)
【在 c********t 的大作中提到】
: 开始套不进knapsack去，因为把限定的value想当做weight的限制。
: 后来发现这个限制应该在benefit value上，只要在knapsack中间，比较一下总value是
: 不是超过limit就行了
|
c********t
发帖数: 5706 | 5 你这样好像不太对，只要P(n-1, K-Ki)意思就是item i一定选择了。我刚刚做出，看我
前面的回文，但不知道还能不能优化。
【在 n*****s 的大作中提到】
:
: 普通的背包是P(n, K)depends on P(n-1, K)或者P(n-1, K-Ki)
: 这个应该只要P(n-1, K-Ki)
|
n*****s
发帖数: 6495 | 6
哦，我想错了
你那样做下来是O(nS)?
【在 c********t 的大作中提到】
: 你这样好像不太对，只要P(n-1, K-Ki)意思就是item i一定选择了。我刚刚做出，看我
: 前面的回文，但不知道还能不能优化。
|
c********t
发帖数: 5706 | 7 是O(mn) 因为m这里才是背包容量。S的用处只是判断了一下来limit max value
【在 n*****s 的大作中提到】
:
: 哦，我想错了
: 你那样做下来是O(nS)?
|
c********t
发帖数: 5706 | 8 唉，好像还是有问题，感觉这道题套不进knapsack
【在 c********t 的大作中提到】
: 是O(mn) 因为m这里才是背包容量。S的用处只是判断了一下来limit max value
|
n*****s
发帖数: 6495 | 9
好像是不行
我又想了一下即使O(nS)的也不行
总不能用brute force吧
难道那个都是整数的条件放在那里是用来误导的
【在 c********t 的大作中提到】
: 唉，好像还是有问题，感觉这道题套不进knapsack
|
c********t
发帖数: 5706 | 10 说实在的，把条件改为=S, 我也只能想出brute force的方法，除非m <=4可以用
hashtable。放弃了。
【在 n*****s 的大作中提到】
:
: 好像是不行
: 我又想了一下即使O(nS)的也不行
: 总不能用brute force吧
: 难道那个都是整数的条件放在那里是用来误导的
|
o**********t
发帖数: 406 | 11 no dup ... so you can sort first -> O(n*Log(n))
Then start picking from smallest.
Total complexity O(n) + O(n*Log(n)), still the same as O(n*Log(n)) |
c********t
发帖数: 5706 | 12 排玩序后，也不可能用O（n)找出m个数
虽然和背包问题不同，但还是可以用DP解, O(m*n*s) time
【在 o**********t 的大作中提到】
: no dup ... so you can sort first -> O(n*Log(n))
: Then start picking from smallest.
: Total complexity O(n) + O(n*Log(n)), still the same as O(n*Log(n))
|
