最少硬币问题

xiaoxiao2021-02-28  11

1.题目

        钱包里有一些硬币,1元,5元,10元,50元,100元,500元,现在用这些硬币去买自动贩卖机里价格为A的饮料。假设自动贩卖机所需金额必须是刚刚好,不能多不能少。问最少需要多少枚硬币         输入:         1元,5元,10元,50元,100元,500元每枚硬币的个数 和 A的值         输出:         凑成A的最少硬币数或者NOWAY

2.动规法解题

       思路:先将当前的面额大的硬币尽量多用,当超过所规定的硬币数量时,去寻找之前硬币所能组成的组合。                子问题划分:二维备忘录dp[i][j] 代表前i种硬币凑成当前金额j所需的最少个数        辅助数组:curCoinNum[i][j]记录第i种硬币在金额为j时用了多少个                  初值:           其中coinNum[i]是第i中硬币的个数            递推方程:         其中coins是6种硬币的面额                 代码: static int[] coins = {-1,1,5,10,50,100,500}; static int n = coins.length-1; static int[] coinNum = new int[n+1]; static int A; static int MAX = Integer.MAX_VALUE; static String DP(){ //curCoinNum[i][j]代表 第i个硬币在价值为j的时候用了几个 int[][] curCoinNum = new int[n+1][A+1]; //动归求解,dp[i][j]表示前i个硬币对于价值j时所需的最小数量 int[][] dp = new int[n+1][A+1]; //初值 for(int i=1;i<=n;i++) for(int j=1;j<=A;j++) dp[i][j] = MAX; //初值 ,当前价值只用第一种硬币组成 for(int j=1;j<=A;j++) if(j <= coinNum[1]) dp[1][j] = j; for(int i=2;i<=n;i++){ for(int j=1;j<=A;j++){ if(coinNum[i]>0 && j>=coins[i]){ //尽量先将当前硬币用光 if(curCoinNum[i][j-coins[i]]+1 <= coinNum[i]){ //若上一个硬币也无法达到j-coins[i]的价值,则当前硬币也无法达到 dp[i][j] = dp[i][j-coins[i]]==MAX?MAX:dp[i][j-coins[i]]+1; curCoinNum[i][j] = curCoinNum[i][j-coins[i]] + 1; }else{ //当前硬币已用尽时 int min = dp[i-1][j]; for(int k=1;k<i;k++){ if(dp[k][j-coins[i]]<MAX && min>(dp[k][j-coins[i]]+1)){ min = dp[k][j-coins[i]]+1; } } if(min < Integer.MAX_VALUE) curCoinNum[i][j] = 1; //若可凑成当前金额,则代表只用了一个当前硬币 dp[i][j] = min; } }else dp[i][j] = dp[i-1][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=A;j++){ System.out.print(curCoinNum[i][j] + " "); } System.out.println(); } if(dp[n][A] == MAX) return "NOWAY"; return dp[n][A]+""; } public static void main(String[] args)throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] input = br.readLine().split(" "); for(int i=1;i<=6;i++){ coinNum[i] = Integer.parseInt(input[i-1]); } A = Integer.parseInt(input[6]); System.out.println( DP()); }

3. 回溯法解题

        思路:此题可转化成为0-1背包问题(将每种硬币乘以其数量),这样一来我们只用考虑取值是1的硬币的个数           输入:n个硬币(面值可相同)         解空间:n+1层高的满二叉树(左1右0)         可行解:A为总金额                     

          最优解:众多可行解中取值为1的硬币最少的解

       代码:

        

static int[] coin = {1,5,10,50,100,500}; static List<Integer> coins; static int A, //初始给定金额 n, //总硬币数 x[], //记录当前硬币的0,1取值 bestx[],//记录最优解的0,1取值 cv, //当前目标金额 bestn, //最少硬币个数 cn; //当前硬币个数 static void Backtrack(int i){ if(i>=n){ if(cv==0){ if(bestn > cn){ for(int j=0;j<n;j++) bestx[j] = x[j]; bestn = cn; } } return; } if(cv >= coins.get(i)){ x[i] = 1; cv -= coins.get(i); cn += 1; Backtrack(i+1); cn -= 1; cv += coins.get(i); } Backtrack(i+1); } public static void main(String[] args)throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = br.readLine().split(" "); A = Integer.parseInt(str[str.length-1]); cv = A; coins = new ArrayList<Integer>(); //将所有硬币化为单个对象,放入集合之中 bestn = Integer.MAX_VALUE; for(int i=str.length-2;i>=0;i--){ int num = Integer.parseInt(str[i]); for(int j=0;j<num;j++){ coins.add(coin[i]); } } n = coins.size(); x = new int[n]; bestx = new int[n]; // for(int i=0;i<coins.size();i++) // System.out.print(coins.get(i)+" "); Backtrack(0); System.out.println(bestn==Integer.MAX_VALUE?"NOWAY":bestn); for(int i=0;i<n;i++){ if(bestx[i] != 0) System.out.println(coins.get(i)); } }

转载请注明原文地址: https://www.6miu.com/read-450179.html

最新回复(0)