关于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.
相关阅读
new grad offer求比较考FE(Fundamentals of Engineering)对电力方面找工有帮助吗？老中最危险10大心态 (转载)狗家扭腰DoubleClick组这么吊啊？大家有没有碰到过4个小时的OA的？上次你软宣传要开源visual studio电影剧组在las vegas招化妆师一名，请推荐或自荐，谢谢!关于F和G家面试地点问题通过了面试却面临身份问题关于H1B transfer中的最后3个paycheck的问题yapstone是什么样的公司？紧急求助湾区 Pre-IPO 小公司招人最近有什么opt stem最新进展么三轮quantitative developer。等offer 求祝福！！！！！！大侠们，公司到底用软件筛简历吗？能贴个适合软件筛选的简历模版吗？请教两个问题讨论一下12306的架构？L家系统设计一题讨论Amazon的OA过后，多久会收到onsite通知？