过年好,生意兴隆# 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))
相关阅读
这种情况能申请NIW 吗？用EAD工作的风险大家在哪儿买回国机票？请教个关于485的cover letter的问题EB1B PP NSC 4-day approval如何用中国知网英文版检索引用？efile 急问，为什么老说我哪里没填完整？弱问485递了之后再问文章检索精准度的问题如果用了AP/EAD combo卡回国其实文章引用率这个事不能只追求高Two Welcome Notices?国内的研究和现在在美国的研究完全不同NSC and TSC关于邮寄地址（TSC还是NSC)交485前，换了工作（同领域），该怎么办11月 18交的 EAD AP, 12月22 EAD 批了, AP 还是 initial review TSC加国可以申请兄弟姐妹来加么EB1B拿到绿卡后多长时间可以换工作？关于I-131，请教Class of Admission的信息在哪里？