算法： 零钱问题

import java.util.Arrays;/*** 问题描述：给定一个数值N，代表钱数。在给定一个表示零钱的子集，S = { S1, S2, … , Sm}* 问题是使用子集中的元素进行零钱兑换，存在多少种兑换方法？零钱的顺序不用考虑。* 
* 举例一：给定数值4，和子集 S = {1,2,3} 那么存在4中兑换方法： {1,1,1,1},{1,1,2},{2,2},{1,3}* 举例二：给定数值10，和子集 S = {2, 5, 3, 6} 那么存在5种兑换方法：{2,2,2,2,2}, {2,2,3,3},* {2,2,6}, {2,3,5} and {5,5}.*/
public class Change {private static int countWays0(int coins[], int size, int total) {if (total == 0)return 1;if (total < 0)return 0;if (size <= 0)return 0;return countWays0(coins, size - 1, total) +countWays0(coins, size, total - coins[size - 1]);}private static long countWays1(int coins[], int size, int total) {long[] table = new long[total + 1];Arrays.fill(table, 0); // O(total)table[0] = 1;for (int i = 0; i < size; i++)for (int j = coins[i]; j <= total; j++)table[j] += table[j - coins[i]];return table[total];}private static int countWays2(int coins[], int size, int total) {int table[] = new int[total + 1];table[0] = 1;//将每种面额都计算一遍for (int i = 0; i < size; i++)//这里从coins[i]开始，表示这种面额只能用于总金额比它大的情况下for (int j = coins[i]; j <= total; j++)//计算当使用当前的面额，不同总金额的数量都需要改变table[j] += table[j - coins[i]];return table[total];}/**** https://blog.csdn.net/zw159357/article/details/82664026* https://blog.csdn.net/S_snowxue/article/details/104743877* 给定不同面额的硬币 coins 和一个总金额 amount。* 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。** @param coins* @param amount* @return*/private static int coinMinChange(int[] coins, int amount) {Arrays.sort(coins);int size = coins.length;if (size == 0 || amount == 0)return 0;int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;for (int j = 0; j < size; j++) {for (int i = coins[j]; i <= amount; i++) {dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}return dp[amount] > amount ? -1 : dp[amount];}public static void main(String[] args) {int coins[] = {1, 2, 3};int size = coins.length;int total = 4;//1,1,1,1//1,2,1//1,3//2,2//多少种方法凑齐System.out.println(countWays0(coins, size, total));System.out.println(countWays1(coins, size, total));System.out.println(countWays2(coins, size, total));//最少凑齐需要多少枚硬币System.out.println(coinMinChange(coins, total));}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！