首页 > Java > java教程 > 正文

动态规划之找零问题详解

零下一度
发布: 2017-07-20 13:35:00
原创
2855 人浏览过

  找零问题:需找零金额为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 <= i <= m)面值的硬币数再加1个di面值的硬币,当然j >= 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 < sum + 1; j++) { //总金额数,1,2,3,……,sum21             int minCoins = j;22             for (int i = 0; i < money.length; i++) {    //遍历硬币的面值23                 if (j - money[i] >= 0) {24                     int temp = count[j - money[i]] + 1; //当前所需硬币数25                     if (temp < minCoins) {26                         minCoins = temp;27                     }28                 }29             }30 31             count[j] = minCoins;32         }33         System.out.println(Arrays.toString(count));34         return count[sum];35     }36 }
登录后复制

  Python3

 1 #coding=utf-8 2 def charge_making(money, num): 3     &#39;&#39;&#39; 4     找零问题 5     &#39;&#39;&#39; 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 < minCoins:14                     minCoins = temp15         16         count[j] = minCoins17     18     return count[num]19 20 money = [1, 3, 2, 5]21 num = 822 count = charge_making(money, num)23 print(count)
登录后复制

tag

以上是动态规划之找零问题详解的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板