高手 求算法

Question

有50个正整数 其中有不定个数的和 等于某一个指定的正整数
求出那些数的和等于那个指定的正整数
算法应该如何写

Answer 1

package com.frog.test;import java.util.ArrayList;public class Qemperor {
ArrayList<Integer> al = new ArrayList<Integer>(50); 
ArrayList<Integer> rl = new ArrayList<Integer>(50); 

public Qemperor(){
//初始化，假设已排序，如果没排序 那么自己排序先
al.add(new Integer(50));
al.add(new Integer(45));
al.add(new Integer(40));
al.add(new Integer(35));
al.add(new Integer(30));
al.add(new Integer(25));
al.add(new Integer(20));
al.add(new Integer(10));
al.add(new Integer(5));
} public boolean compute(Integer left, int index ){
if(left == 0){
return true;
}else if(index >= al.size()){
return false;
}else if(left > 0){
rl.add(al.get(index));
al.remove(index);
return compute(left - rl.get(rl.size()-1),index);
}else{
al.add(0,rl.get(rl.size()-1));
rl.remove(rl.size()-1);
return compute(left + al.get(0),++index);
}
}
public void print(){
System.out.println("reault list:");
for(int i=0; i<rl.size(); i++){
System.out.println(rl.get(i));
}
System.out.println("data left list:");
for(int i=0; i<al.size(); i++){
System.out.println(al.get(i));
}

}
public static void main(String[] args) {
Qemperor q = new Qemperor();
if(q.compute(75, 0)){
q.print();
System.out.println("Yes");
}else{
System.out.println("Oh no!");
}
}}

Answer 2

1.lz 这个问题不是排序的问题，也不是排列组合
算法上叫 背包问题，你可以搜下，
2.我上面给出了一个 java 的程序 求得一个解 ，排序是为了优化算法，
3.如果求 全解算法 比求一个解算法复杂多了