找零问题:需找零金额为W,硬币面值有(d1, d2, d3,…,dm),最少需要多少枚硬币。
问题:需找零金额为8,硬币面值有(1, 3, 2, 5),最少需要多少枚硬币。
设F(j)表示总金额为j时最少的零钱数,F(0) = 0,W表示找零金额,有零钱一堆{d1, d2, d3,…,dm}。同样根据之前的经验,要达到为j,那么必然是j – di(1 = di,即F(j) = F(j - di) + 1, j >= di。
Java
1 package com.algorithm.dynamicprogramming; 2 3 import java.util.Arrays; 4 5 /** 6 * 找零问题 7 * Created by yulinfeng on 7/5/17. 8 */ 9 public class Money {10 public static void main(String[] args) {11 int[] money = {1, 3, 2, 5};12 int sum = 8;13 int count = money(money, sum);14 System.out.println(count);15 }16 17 private static int money(int[] money, int sum) {18 int[] count = new int[sum + 1];19 count[0] = 0;20 for (int j = 1; j = 0) {24 int temp = count[j - money[i]] + 1; //当前所需硬币数25 if (temp
python3
1 #coding=utf-8 2 def charge_making(money, num): 3 ''' 4 找零问题 5 ''' 6 count = [0] * (num + 1) 7 count[0] = 0 8 for j in range(1, num + 1): 9 minCoins = j10 for i in range(len(money)):11 if j - money[i] >= 0:12 temp = count[j - money[i]] + 113 if temp
tag
以上就是动态规划之找零问题详解的详细内容,更多请关注php中文网其它相关文章!
Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号