java实现购物券消费方案

公司发了某商店的购物券1000元，限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,…，要求程序列出所有的正好能消费完该购物券的不同购物方法。

程序输入：

第一行是一个整数m，代表可购买的商品的种类数。

接下来是m个整数，每个1行，分别代表这m种商品的单价(0<m<1000)。

程序输出：

第一行是一个整数，表示共有多少种方案

第二行开始，每种方案占1行，表示对每种商品购买的数量，中间用空格分隔。

例如：

输入：

2

200

300

则应输出：

2

2 2

5 0

输入：

2

500

800

则应输出：

1

2 0

输入：

1

999

则应输出：

0

多个方案间的顺序不重要。

package com.liu.ex3;

import java.util.ArrayList;

import java.util.Scanner;

public class Main {

    public static ArrayList<Integer> list = new ArrayList<Integer>();

    public static int[][] value;

    public static int m;

    public static int count = 0;

    public static String result = "";

    public void dfs(int sum, int step) {

        if(step == m) {

            if(sum == 1000) {

                for(int i = 0;i < list.size();i++) {

                    result += list.get(i)+" ";

                }

                result += "\n";

                count++;

            }

            return;

        } else {

            for(int i = 0;i <= value[step][1];i++) {

                sum += value[step][0] * i;

                list.add(i);

                dfs(sum, step + 1);

                sum -= value[step][0] * i;

                list.remove(list.size() - 1);

            }

        }

    }

    public static void main(String[] args) {

        Main test = new Main();

        Scanner in = new Scanner(System.in);

        m = in.nextInt();

        value = new int[m][2];

        for(int i = 0;i < m;i++) {

            int a = in.nextInt();

            int num = 1000 / a;

            value[i][0] = a;

            value[i][1] = num;

        }

        test.dfs(0, 0);

        if(count == 0)

            System.out.println("0");

        else

            System.out.println(count+"\n"+result);

    }

}

巴特西

java实现购物券消费方案

最新文章

热门文章