货币组合问题

Question

1.输入若干个正整数 A1,A2,A3... ，比如（3,5,9...),至少输入1个
2.输入一个正整数S（这个数必须大于等于之前输入的任何一个数)
3.计算 如何组合 A1,A2,A3... 加起来和等于 S
4.要求：A1,A2,A3... 不一定都要用到，但是用到的 A 的数量最少
5.如果任意组合都无法满足和等于S，就返回错误比如: A[]=1,2,5 ; S=6
那么最佳结果就是： 5+1=6

Answer 1

此回复为自动发出,仅用于显示而已，并无任何其他特殊作用
楼主【xfcrab】截止到2008-07-17 16:51:54的历史汇总数据(不包括此帖)：
发帖的总数量:2                        发帖的总分数:2                        每贴平均分数:1                        
回帖的总数量:3                        得分贴总数量:0                        回帖的得分率:0%                       
结贴的总数量:1                        结贴的总分数:0                        
无满意结贴数:0                        无满意结贴分:0                        
未结的帖子数:1                        未结的总分数:2                        
结贴的百分比:50.00 %               结分的百分比:0.00  %                  
无满意结贴率:0.00  %               无满意结分率:---------------------
楼主加油

Answer 2

最直接的办法就是用穷举法了。1个为组合，2个为组合...n个为组合（n就是你A的个数）。

Answer 3

int s = 6;
List a = new ArrayList();
a.add("1");
a.add("2");
a.add("5");
java.util.Collections.sort(a,new Comparator(){
public int compare(Object arg0, Object arg1) {
if(arg0 instanceof String && arg1 instanceof String){
int a0=Integer.parseInt((String)arg0);
int a1=Integer.parseInt((String)arg1);
if(a0==a1)return 0;
if(a0>a1)return -1;
}
return 1;
}
});
List result = new ArrayList();
int value=0;
while(value<s){
for(Iterator itr = a.iterator();itr.hasNext();){
int c =Integer.parseInt(itr.next().toString());
if(c>s)itr.remove();
if(c+value<=s){
value+=c;
itr.remove();
result.add(""+c);
break;
}
}
if(value==s)break;
}
if(value==s){//有正解
for(Iterator itr = result.iterator();itr.hasNext();){
System.out.print(itr.next()+"  ");
}
}else{
System.out.println("没有正确答案.");
}

Answer 4

public class Test01 {    public static void main(String[] args) {
        int[] a = {1,2,5};
        Arrays.sort(a);
        int s = 23;
        
        StringBuffer sb = new StringBuffer();
        sb.append(s).append("=");
        for(int i = a.length - 1, k = 0; i >= 0; i--) {
            while(s >= a[i]) {
                s -= a[i];
                if(k > 0) {
                    sb.append("+");
                }
                k++;
                sb.append(a[i]);
            }
        }
        if(s == 0) {
            System.out.println(sb.toString());
        } else {
            System.out.println("Error!");
        }
    }
}

Answer 5

这个还真不好测试
如果从实际出发，那大家都知道我国货币为{1，2，5，……}，那6楼的可以满足要求，因为设计为这几个值的规律是后一个可以由前几个数计算得到，所以不用回溯。
但如果按楼主的，货币基准是用户定制的，完全可以{3，4，5}，只不过这种不太合理而已。那么例如16=2*5+2*3，6楼的就不行了另外，5楼的更是糟糕，只要随便一个稍微大点的数，对于{1，2，5}只要s是9就死循环~~~~show下我的，欢迎质疑，第二个函数纯粹只是为了格式化输出    public static int[] calcAsArray(int money, int[] baseCurrency){
        if(baseCurrency == null){
            baseCurrency = new int[]{1, 2, 5};
        }
        Arrays.sort(baseCurrency);
        int[] coe = new int[baseCurrency.length];
        for(int i = 0; i < coe.length; i++){
            coe[i] = 0;
        }        int temp = money;
        int i, j;
        for(i = baseCurrency.length - 1; i >= 0; i--){
            coe[i] = temp/baseCurrency[i];
            temp -= coe[i] * baseCurrency[i];
            if(temp == 0){//组合成功
                break;
            }
            if(i == 0){ //扫描完毕，组合不成功。回溯，重新初始化
                for(j = 0; j < coe.length; j++){
                    if(coe[j] != 0){
                        coe[j]--;
                        i = j - 1;
                        temp += baseCurrency[j];
                    } else if(j == coe.length){//无法组合成功
                        return null;
                    }
                }
            }
        }
        if(temp != 0){
            return null;
        }
        return coe;
    }    public static String calcAsString(int money, int[] baseCurrency){
        int[] coe = calcAsArray(money, baseCurrency);
        if(coe == null)return "Error";
        StringBuffer sb = new StringBuffer();
        for(int i = coe.length - 1; i >= 0 ; i--){
            if(coe[i] == 1){
                sb.append(baseCurrency[i]).append(" + ");
            }else if(coe[i] > 1){
                sb.append(coe[i]).append(" * ").append(baseCurrency[i]).append(" + ");
            }
        }
        sb.deleteCharAt(sb.lastIndexOf("+"));
        sb.append(" = ").append(money);        return sb.toString();
    }

Answer 6

7楼你的算法也不对，怎么搞出乘法了。下面是我的算法：import java.util.Vector;
public class Combination {
public static void main(String[] args) {
Combination c = new Combination(new int[]{2,4,6,8,9,10}, 12);
c.getResult();
}

private int[] candidates = null;
private int target = 0;

public Combination(int[] cand, int target){
this.candidates = cand;
this.target = target;
}

public void getResult(){
for(int i=0; i<candidates.length; i++){
if(candidates[i]==target){
System.out.println(""+candidates[i]+"="+target);
}
explore(new int[]{candidates[i]}, i+1);
}
}

public void explore(int[] curr, int i){
for(int j=i; j<candidates.length; j++){
if(sun(curr)+candidates[j]==target){
printResult(curr, candidates[j]);
}else if(sun(curr)+candidates[j]<target){
int[] curr2 = new int[curr.length+1];
System.arraycopy(curr, 0, curr2, 0, curr.length);
curr2[curr2.length-1] = candidates[j];
explore(curr2, i+1);
}
}
}

public int sun(int[] arr){
int sun = 0;
for(int i=0; i<arr.length; i++){
sun += arr[i];
}
return sun;
}

public void printResult(int[] curr, int last){
for(int i=0; i<curr.length; i++){
System.out.print(""+curr[i]+"+");
}
System.out.print(""+last+"=");
System.out.println(target);
} }

Answer 7

不好意思，粗心大意加单元测试没做好。有个变量名写错了，这个程序才对：public class Combination {
public static void main(String[] args) {
Combination c = new Combination(new int[]{2,3,4,5,6,7,8,9,10}, 12);
c.getResult();
}

private int[] candidates = null;
private int target = 0;

public Combination(int[] cand, int target){
this.candidates = cand;
this.target = target;
}

public void getResult(){
for(int i=0; i<candidates.length; i++){
if(candidates[i]==target){
System.out.println(""+candidates[i]+"="+target);
}
explore(new int[]{candidates[i]}, i+1);
}
}

public void explore(int[] curr, int i){
for(int j=i; j<candidates.length; j++){
if(sun(curr)+candidates[j]==target){
printResult(curr, candidates[j]);
}else if(sun(curr)+candidates[j]<target){
int[] curr2 = new int[curr.length+1];
System.arraycopy(curr, 0, curr2, 0, curr.length);
curr2[curr2.length-1] = candidates[j];
explore(curr2, j+1);
}
}
}

public int sun(int[] arr){
int sun = 0;
for(int i=0; i<arr.length; i++){
sun += arr[i];
}
return sun;
}

public void printResult(int[] curr, int last){
for(int i=0; i<curr.length; i++){
System.out.print(""+curr[i]+"+");
}
System.out.print(""+last+"=");
System.out.println(target);
} }

Answer 8

看来题目的理解就不一样！！我理解的是：任意一个数，用基准数进行组合，要求用到的最少（就是硬币找零问题，用最少的硬币数）。
比如基准为{3，4，5}，那么组合5就是1个5，组合10就是2个5（当然可以2个3一个4，但这样就不是最少了），组合16就是2个5、2个3。乘法不就是表示数量嘛。不知qj123456_0是怎么理解题目的。
当基准为{3，4，5}时，16就不能组合了？而且你输出所有可能的组合有什么用的，不是已经限定了“用到的 A 的数量最少”吗？