列出购物方法


题:
公司发了某商店的购物券1000元,限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,…,要求程序列出所有的正好能消费完该购物券的不同购物方法。
程序输入:
第一行是一个整数m,代表可购买的商品的种类数。
接下来是m个整数,每个1行,分别代表这m种商品的单价。
程序输出:
第一行是一个整数,表示共有多少种方案
第二行开始,每种方案占1行,表示对每种商品购买的数量,中间用空格分隔。
例如:
输入:
2
200
300
则应输出:
2
2 2
5 0
输入:
2
500
800
则应输出:
1
2 0

源码ShoppingGame.java


import java.util.Scanner;

public class ShoppingGame {
    
    private static String go(int[] a) {
        int[] b = new int[a.length];
        return go(a, b, 0);
    }
    private static String go(int[] a, int[] b, int x) {
        if (x==a.length) {
            int r = 0;
            for (int i=0; i<a.length; i++) {
                r += a[i]*b[i];
            }
            String s = "";
            if (r==1000) {
                for (int i:b) {
                    s += i+" ";
                }
                s += "\n";
            }
            return s;
        }
        String t = "";
        int[] c = b.clone();// Critical
        for (int i=0; a[x]*i<=1000; i++) {
            String tm = go(a, c, x+1);
            if (tm!="") t += tm;
            c[x] += 1;
        }
        return t;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();
        String s = go(a);
        System.out.println(s.length()/(2*n+1));
        System.out.println(s);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注