Java教程

贪心算法——Java实现

本文主要是介绍贪心算法——Java实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

概念:

贪心的意思在于在作出选择时,每次都要选择对自身最为有利的结果,保证自身利益的最大化。

题目:

小明手中有 1,5,10,50,100 五种面额的纸币,每种纸币对应张数分别为 5,2,2,3,5 张。若小明需要支付 456 元,则需要多少张纸币?

解题思路:

  • 建立数学模型来描述问题 

设小明每次选取一张面额为Xi的纸币,总共选择n张,则剩余待支付金额为R。

  • 把求解的问题分成若干个子问题 

小明选择纸币进行支付的过程,可以划分为n个子问题:即每个子问题对应为:
在未超过456的前提下,在剩余的纸币中选择一张纸币。

  • 对每个子问题求解,得到子问题的局部最优解

在允许的条件下选择面额最大的纸币。

第一次选取100元,则R=456-100=356;

第二次选取100元,则R=356-100=256;

第三次选取100元,则R=256-100=156;

第四次选取100元,则R=156-100=56;

第五次选取50元,则R=56-50=6;

第六次选取5元,则R=6-5=1;

第七次选取1元,则R=1-1=0;

  • 把子问题的解局部最优解合成原来解问题的一个解

小明总共需要100元*4张+50元*1张+5元*1张+1元*1张。

 1 public class GreedyAlgorithmTest {
 2     private final int n = 5;
 3     private int[] count = {5,2,2,3,5};
 4     private int[] value = {1,5,10,50,100};
 5     
 6     @Test
 7     public void moneyNumber(){
 8         int money = 456;
 9         int num = 0;
10         for (int i = n-1; i >=0; i--) {
11             int min = Math.min(money / value[i], count[i]);
12             money = money - min*value[i];
13             num = num + min;
14         }
15         if (money>0){
16             num = -1;
17         }
18         System.out.println(num);
19     }
20 }

 

 

 

这篇关于贪心算法——Java实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!