过年好,生意兴隆# Immigration - 落地生根
c*t
1 楼
从n个无重复正整数的数组里选m个数，要求这m个数的总和是<=S的最大解。
比如 从{1,3,9,15} 选 m=2个,<=13, 答案就是{3,9}。如果<=10,答案就是{1,9}
比如 从{1,3,9,15} 选 m=2个,<=13, 答案就是{3,9}。如果<=10,答案就是{1,9}
m*l
2 楼
好
n*s
3 楼
knapsack吧
2个dependency变成1个就行 O(mS)
2个dependency变成1个就行 O(mS)
H*O
4 楼
chi
【在 m*******l 的大作中提到】
: 好
【在 m*******l 的大作中提到】
: 好
c*t
5 楼
开始套不进knapsack去，因为把限定的value想当做weight的限制。
后来发现这个限制应该在benefit value上，只要在knapsack中间，比较一下总value是
不是超过limit就行了
【在 n*****s 的大作中提到】
: knapsack吧
: 2个dependency变成1个就行 O(mS)
后来发现这个限制应该在benefit value上，只要在knapsack中间，比较一下总value是
不是超过limit就行了
【在 n*****s 的大作中提到】
: knapsack吧
: 2个dependency变成1个就行 O(mS)
A*n
6 楼
baozi?
【在 m*******l 的大作中提到】
: 好
【在 m*******l 的大作中提到】
: 好
n*s
7 楼
普通的背包是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
8 楼
你这样好像不太对，只要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 的大作中提到】
:
: 普通的背包是P(n, K)depends on P(n-1, K)或者P(n-1, K-Ki)
: 这个应该只要P(n-1, K-Ki)
n*s
9 楼
哦，我想错了
你那样做下来是O(nS)?
【在 c********t 的大作中提到】
: 你这样好像不太对，只要P(n-1, K-Ki)意思就是item i一定选择了。我刚刚做出，看我
: 前面的回文，但不知道还能不能优化。
c*t
10 楼
是O(mn) 因为m这里才是背包容量。S的用处只是判断了一下来limit max value
【在 n*****s 的大作中提到】
:
: 哦，我想错了
: 你那样做下来是O(nS)?
【在 n*****s 的大作中提到】
:
: 哦，我想错了
: 你那样做下来是O(nS)?
c*t
11 楼
唉，好像还是有问题，感觉这道题套不进knapsack
【在 c********t 的大作中提到】
: 是O(mn) 因为m这里才是背包容量。S的用处只是判断了一下来limit max value
【在 c********t 的大作中提到】
: 是O(mn) 因为m这里才是背包容量。S的用处只是判断了一下来limit max value
n*s
12 楼
好像是不行
我又想了一下即使O(nS)的也不行
总不能用brute force吧
难道那个都是整数的条件放在那里是用来误导的
【在 c********t 的大作中提到】
: 唉，好像还是有问题，感觉这道题套不进knapsack
c*t
13 楼
说实在的，把条件改为=S, 我也只能想出brute force的方法，除非m <=4可以用
hashtable。放弃了。
【在 n*****s 的大作中提到】
:
: 好像是不行
: 我又想了一下即使O(nS)的也不行
: 总不能用brute force吧
: 难道那个都是整数的条件放在那里是用来误导的
hashtable。放弃了。
【在 n*****s 的大作中提到】
:
: 好像是不行
: 我又想了一下即使O(nS)的也不行
: 总不能用brute force吧
: 难道那个都是整数的条件放在那里是用来误导的
o*t
14 楼
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))
Then start picking from smallest.
Total complexity O(n) + O(n*Log(n)), still the same as O(n*Log(n))
c*t
15 楼
排玩序后，也不可能用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))
虽然和背包问题不同，但还是可以用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))
相关阅读
SR 3 days, EAD approved我也绿了EB1A non-pp ref 求解 并求祝福。又是review问题有统计表明pp会极大增加eb1a rfe 风险么？Employment verification媒体报道里面引用我文章，算citation吗？在要求打指文的时候, 会问哪些问题?请教F-1申请绿卡的考虑08年3月的EB2啥时候能递交485485和党员问题，付解释信模板TX IO 206 求助485 和 体检表的地址问题请问老大，book review的问题请教F1 退学与485批准的影响这些东西用来支持contribution还是authorship？移民美国（劳工移民EW-3）亲历记-9 终结篇为什么打完指纹三天，都没有soft LUD？到底还是悲剧了开会怎么和大牛们陶瓷？