找零问题:需找零金额为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 ''' 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 < 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中文网其他相关文章!

本文讨论了使用Maven和Gradle进行Java项目管理,构建自动化和依赖性解决方案,以比较其方法和优化策略。

本文使用Maven和Gradle之类的工具讨论了具有适当的版本控制和依赖关系管理的自定义Java库(JAR文件)的创建和使用。

本文讨论了使用咖啡因和Guava缓存在Java中实施多层缓存以提高应用程序性能。它涵盖设置,集成和绩效优势,以及配置和驱逐政策管理最佳PRA

本文讨论了使用JPA进行对象相关映射,并具有高级功能,例如缓存和懒惰加载。它涵盖了设置,实体映射和优化性能的最佳实践,同时突出潜在的陷阱。[159个字符]

Java的类上载涉及使用带有引导,扩展程序和应用程序类负载器的分层系统加载,链接和初始化类。父代授权模型确保首先加载核心类别,从而影响自定义类LOA


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

VSCode Windows 64位 下载
微软推出的免费、功能强大的一款IDE编辑器

SublimeText3 Linux新版
SublimeText3 Linux最新版

ZendStudio 13.5.1 Mac
功能强大的PHP集成开发环境

SublimeText3 英文版
推荐:为Win版本,支持代码提示!

Atom编辑器mac版下载
最流行的的开源编辑器