Question

急求：有序数组的一个算法问题，谢谢！

如何在一个有序数组中（比如10，7，6，6，4，3，2，1）中挑选k个数（k从1到n），使得它们的和为s(s为数组中最大的那个数，也就是第一个数)。
请问除了枚举有什么好方法吗？（k从1开始递增，需要给出所有情况）
谢谢!

Answer 1

采用动态规划算法，经典的背包问题。

f(i,j)为使用i个数使它们的和为j，是否可能。
如果可能，f(i,j)=true,否则为false.

这样对所有的数字循环，有f(i,j)=f(i,j) or f(i-1,j-num[k])
num[k]是所有的数字循环一次。

这样按照i,j递增的顺序就可以得到结果。想要得到原先的选数还要另外设置g(i,j)保存使f(i,j)变为true的k。向上找就可以找到答案。

我要睡觉了所以写的不清楚。

想知道的话请百度关键字：背包问题 动态规划

Answer 2

用递归函数不是很好做?

数组int tab(1:n)
函数fun(int tab(1:n),k,s)

那么 fun(int tab(1:n),k,s)=fun(int tab(2:n),k,s),fun(int tab(1:n),k-1,s-tab(1))

即从1~n中挑选k个数的问题,其实分成两种情况:
1.数组的第一个数不选,那么从2~n中挑选k个数,使和为s
2.选第一个数,那么从2~n中挑选k-1个数,使和为(s-数组的第一个数)

然后只要写收敛条件就可以了,即当n=k时,如果s=sum(tab(1:n)),打印,否则直接返回