关于n个数的所有和的一个问题# JobHunting - 待字闺中
m*f
1 楼
假设有n个数（均为正整数），把这ｎ个数中的若干个数相加，每个数
最多用一次，我们最多能够得到２︿ｎ－１种和，现在我们需要求出其中
第ｉ小的那个数，怎么求？？多项式时间能够搞定么？？
最多用一次，我们最多能够得到２︿ｎ－１种和，现在我们需要求出其中
第ｉ小的那个数，怎么求？？多项式时间能够搞定么？？
r*o
2 楼
用DP算法可否?
假定这n个数(a[1], a[2], ... ,a[n])的和为SUM,
A(k,s)＝1表示可以找出k个数的和为s，=0则表示找不出。
A(k,s)=1 if A(k-1, s-a[j])=1, s=1...SUM, k=1,,,.n，j=1,...,n
然后从A(n,1)到A(n,SUM)中找出＝1的那个第i小的数。
【在 m*****f 的大作中提到】
: 假设有n个数（均为正整数），把这ｎ个数中的若干个数相加，每个数
: 最多用一次，我们最多能够得到２︿ｎ－１种和，现在我们需要求出其中
: 第ｉ小的那个数，怎么求？？多项式时间能够搞定么？？
假定这n个数(a[1], a[2], ... ,a[n])的和为SUM,
A(k,s)＝1表示可以找出k个数的和为s，=0则表示找不出。
A(k,s)=1 if A(k-1, s-a[j])=1, s=1...SUM, k=1,,,.n，j=1,...,n
然后从A(n,1)到A(n,SUM)中找出＝1的那个第i小的数。
【在 m*****f 的大作中提到】
: 假设有n个数（均为正整数），把这ｎ个数中的若干个数相加，每个数
: 最多用一次，我们最多能够得到２︿ｎ－１种和，现在我们需要求出其中
: 第ｉ小的那个数，怎么求？？多项式时间能够搞定么？？
b*e
3 楼
明显不行.
If there exists a polynomial procedure for this problem, then I can
applied this procedure with binary search to solve knapsack problem in
polynomial time.
【在 m*****f 的大作中提到】
: 假设有n个数（均为正整数），把这ｎ个数中的若干个数相加，每个数
: 最多用一次，我们最多能够得到２︿ｎ－１种和，现在我们需要求出其中
: 第ｉ小的那个数，怎么求？？多项式时间能够搞定么？？
If there exists a polynomial procedure for this problem, then I can
applied this procedure with binary search to solve knapsack problem in
polynomial time.
【在 m*****f 的大作中提到】
: 假设有n个数（均为正整数），把这ｎ个数中的若干个数相加，每个数
: 最多用一次，我们最多能够得到２︿ｎ－１种和，现在我们需要求出其中
: 第ｉ小的那个数，怎么求？？多项式时间能够搞定么？？
g*y
4 楼
niu～
can also use it to solve subset sum ?
【在 b***e 的大作中提到】
: 明显不行.
: If there exists a polynomial procedure for this problem, then I can
: applied this procedure with binary search to solve knapsack problem in
: polynomial time.
can also use it to solve subset sum ?
【在 b***e 的大作中提到】
: 明显不行.
: If there exists a polynomial procedure for this problem, then I can
: applied this procedure with binary search to solve knapsack problem in
: polynomial time.
m*f
5 楼
明白了， 多谢
【在 b***e 的大作中提到】
: 明显不行.
: If there exists a polynomial procedure for this problem, then I can
: applied this procedure with binary search to solve knapsack problem in
: polynomial time.
【在 b***e 的大作中提到】
: 明显不行.
: If there exists a polynomial procedure for this problem, then I can
: applied this procedure with binary search to solve knapsack problem in
: polynomial time.
相关阅读
这里怎么没人讨论Yahoo的面试呢有没有人interview salesforce过？onsite 之后多久有消息倾家荡产发完了，再问问negotiate salary关于还没有收到H1b正式批准书之前离境的问题用一个offer催另一公司做hiring decision要注意什么？女生面试onsite需要coach包么？今天遇到一个很nice的中国人给我phone interview本版上过去的一些帖子为什么会突然无法访问了呢我发现一个问题请教一道google面试算法题老公F1 OPT期间，我能从H1B转成F2吗？为什么感觉良好的interview都fail了呢郁闷死了，约了电话面试，根本没听见铃声，对方就给留了个言下周二小公司onsite求祝福到底是RECRUTER 找我还是公司招？面试中关于'图'的算法题出线的好像很少阿?是错觉么 还是确实如Job Opportunity for SASSalary 疑问电话面经（Microsoft, Amazon, Google, ...)