用户名：xxxx66yyyy
文章数：107
评论数：419
访问量：1753685
注册日期：
阅读量：1297
阅读量：3317
阅读量：460144
阅读量：1144594
51CTO推荐博文
动态规划的基本思想是将待求解问题分解成若干个子问题，先求解子问题，并将这些子问题的解保存起来，如果以后在求解较大子问题的时候需要用到这些子问题的解，就可以直接取出这些已经计算过的解而免去重复运算。保存子问题的解可以使用填表方式，例如保存在数组中。
用一个实际例子来体现动态规划的算法思想&&硬币找零问题。
硬币找零问题描述：现存在一堆面值为 V1、V2、V3 & 个单位的硬币，问最少需要多少个硬币才能找出总值为 T 个单位的零钱？假设这一堆面值分别为 1、2、5、21、25 元，需要找出总值 T 为 63 元的零钱。
很明显，只要拿出 3 个 21 元的硬币就凑够了 63 元了。
基于上述动态规划的思想，我们可以从 1 元开始计算出最少需要几个硬币，然后再求 2 元、3元&每一次求得的结果都保存在一个数组中，以后需要用到时则直接取出即可。那么我们什么时候需要这些子问题的解呢？如何体现出由子问题的解得到较大问题的解呢？
其实，在我们从 1 元开始依次找零时，可以尝试一下当前要找零的面值（这里指 1&元）是否能够被分解成另一个已求解的面值的找零需要的硬币个数再加上这一堆硬币中的某个面值之和，如果这样分解之后最终的硬币数是最少的，那么问题就得到答案了。
单是上面的文字描述太抽象，先假定以下变量：
values[] : 保存每一种硬币的币值的数组
valueKinds :币值不同的硬币种类数量，即values[]数组的大小
money : 需要找零的面值
coinsUsed[] : 保存面值为 i 的纸币找零所需的最小硬币数
算法描述：
当求解总面值为 i 的找零最少硬币数 coinsUsed[ i ] 时，将其分解成求解 coinsUsed[ i&& cents]和一个面值为&cents&元的硬币，由于 i&& cents & i ， 其解 coinsUsed[ i&& cents] 已经存在，如果面值为 cents 的硬币满足题意，那么最终解 coinsUsed[ i ] 则等于 coinsUsed[ i&& cents] 再加上 1（即面值为 cents）的这一个硬币。
下面用代码实现并测试一下：
public&class&CoinsChange&{ &&&&&&&&&&&&&&&&&&&&&public&static&void&makeChange(int[]&values,&int&valueKinds,&int&money, &&&&&&&&&&&&&int[]&coinsUsed)&{ &&&&&&&&&&coinsUsed[0]&=&0; &&&&&&&&&&&&&&&&&&for&(int&cents&=&1;&cents&&=&&cents++)&{ &&&&&&&&&&&&&&&&&&&&&&&&&&&int&minCoins&=& &&&&&&&&&&&&&&&&&&&&&&&&&&&for&(int&kind&=&0;&kind&&&valueK&kind++)&{&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if&(values[kind]&&=&cents)&{ &&&&&&&&&&&&&&&&&&&&&int&temp&=&coinsUsed[cents&-&values[kind]]&+&1; &&&&&&&&&&&&&&&&&&&&&if&(temp&&&minCoins)&{ &&&&&&&&&&&&&&&&&&&&&&&&&minCoins&=& &&&&&&&&&&&&&&&&&&&&&} &&&&&&&&&&&&&&&&&} &&&&&&&&&&&&&} &&&&&&&&&&&&&&&&&&&&&&&&&&coinsUsed[cents]&=&minC &&&&&&&&&&&&&&System.out.println(&面值为&&&+&(cents)&+&&&的最小硬币数&:&&&&&&&&&&&&&&&&&&&&&&&+&coinsUsed[cents]); &&&&&&&&&} &&&&&} &&&&& &&&&&public&static&void&main(String[]&args)&{ &&&&&&&&&&&&&&&&&&&int[]&coinValue&=&new&int[]&{&25,&21,&10,&5,&1&}; &&&&&&&&&&&&&&&&&&int&money&=&63; &&&&&&&&&&&&&&&&&&int[]&coinsUsed&=&new&int[money&+&1]; &&&&&&&&&&makeChange(coinValue,&coinValue.length,&money,&coinsUsed); &&&&&} &}&
测试结果：
面值为 1 的最小硬币数 : 1
面值为 2 的最小硬币数 : 2
面值为 3 的最小硬币数 : 3
面值为 4 的最小硬币数 : 4
面值为 5 的最小硬币数 : 1
面值为 6 的最小硬币数 : 2
面值为 60 的最小硬币数 : 3
面值为 61 的最小硬币数 : 4
面值为 62 的最小硬币数 : 4
面值为 63 的最小硬币数 : 3
&上面的代码并没有给出具体应该是哪几个面值的硬币，这个可以再使用一些数组保存而打印出来。
了这篇文章
类别：┆阅读(0)┆评论(0)
16:43:53 23:41:11 10:57:41 10:28:20 15:50:22动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度， 因此它比回溯法、暴力法等要快许多。动态规划也是面试笔试题中的一个考查重点，当阅读一个题目并且开始尝试解决它时，首先看一下它的限制。 如果要求在多项式时间内解决，那么该问题就很可能要用DP来解。遇到这种情况， 最重要的就是找到问题的“状态”和“状态转移方程”。(状态不是随便定义的， 一般定义完状态，你要找到当前状态是如何从前面的状态得到的， 即找到状态转移方程)如果看起来是个DP问题，但你却无法定义出状态，
那么试着将问题规约到一个已知的DP问题。
这里先说明一个最简单的动态规划实例：硬币问题。后续还会给出更多的实例，例如：最长公共子序列，最长公共子串，最长递增子序列，字符串编辑距离等。动态规划的关键就是找出“状态”和“状态转移方程”。
硬币问题：给你一些面额的硬币，然后给你一个值N，要你求出构成N所需要的最少硬币的数量和方案。分析：这个问题可以尝试用贪心算法去解决，先从面额最大的硬币开始尝试，一直往下找，知道硬币总和为N。但是贪心算法不能保证能够找出解（例如，给,2,3,5,然后N=11）。我们可以换个思路，我们用d(i)表示求总和为i的最少硬币数量（其实就是动态规划中的“状态”）,那么怎么从前面的状态（并不一定是d(i-1)这一个状态）到d(i)这个状态？假设硬币集合为coins[0~N]，在求d(i)之前，我们假设d(1~i-1)全部都求出来了，那么d(i)=min{d(j)+1},if
i-j 在coins中（其实这就是“状态转移方程”）。举例说明：coins={2,3,5}，N=11。
d(2)=d(0)+1=1;
d(3)=d(0)+1=1;
d(4)=d(2)+1=2;
d(5)=min{d(3)+1,d(2)+1,d(0)+1}=1;
d(6)=min{d(4)+1,d(3)+1}=2;
.......................
同时为了求出最后的方案（不仅仅是硬币个数），需要记录求每个状态选择的“路径”，例如:求d(5)我们选择了d(0)+1，那么我们选择的路径就是5-0=5。我们必须记录这些路径，然后根据路径得出结果。对于d(6)，我们开始选择了3,也就是说我们选择了从d(3)状态和硬币3跳转到d(6),接着对于d(3)，我们选择了3，也就是说我们选择了从d(0)状态和硬币3跳转到了d(3)，接着对于d(0)，这个是初始状态。所以我们得方案是3,3。
如果上面说得还不够清晰，可以参照下面JAVA实现的代码：
* @author kerry
* 给定制定面值的硬币 ，并给出一个值，要求求出硬币综合为这个值需要的最少的硬币的个数，并具体的方案
public class MinCoins {
* @param args
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] coins={1,3,5};
int value=100;
int[] solu=new int[value];
int min=new MinCoins().solution(coins,value,solu);
for(int i=value-1;i&=0;){
System.out.print(solu[i]+&-&&);
i=i-solu[i];
System.out.println();
System.out.println(min);
private int solution(int[] coins,int value, int[] solu){
int[] mins = new int[value+1];
mins[0]=0;
for(int i=1;i&=i++) mins[i]=Integer.MAX_VALUE;
for(int i=1;i&=i++){
for(int j=0;j&coins.j++){
if(coins[j]&=i&&mins[i]&mins[i-coins[j]]+1){
mins[i]=mins[i-coins[j]]+1;
solu[i-1]=coins[j];
return mins[value];
}如果错误，还请多多指出~
本文已收录于以下专栏：
相关文章推荐
动态规划把问题分为子为题
算法 推荐阅读：从动态规划新手到专家
上面是在网上看到的一篇好文章，里面有一个凑硬币的问题
如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？ (表面上这道题可以用贪心算法...
人生苦短，都说必须python，那么我分享下我是如何从小白成为Python资深开发者的吧。2014年我大学刚毕业..
http://blog.csdn.net/cattycat/article/details/5813307
算法导论上第16-1问题
考虑用最少的硬币数找n分钱的问题，假设每个硬币的...
public class Test {
public static int sum = 21;//硬币总和
public static int n = 4;//硬币类型数
public stat...
之前我在动态规划(dynamic programming)原理抛出了一个最少硬币问题。接下来，在这篇文章，我们将会对硬币问题进行一个全面的解析，并尽可能的解释动态规划的原理，希望读者们可以通过这个问题...
算法描述：
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。基本思想也是将待求解问题分解成若干个子问题，先求解子...
看了雷霄骅的故事，为之深表惋惜，一位为科研埋头奉献发光发热的人，这件事也促使我开通博客，来记录自己一点学习的过程。
最近在看动态规划的内容，看了硬币找零问题，是一个很好的对动态规划算法入门的问题，问题...
有一个机器人 在(1,1)位置，在m*n的木板上放着硬币，1代表有，0代表无，机器人只能向下或者向右走，求能收集到的最大硬币。
利用动态规划，在第一行和第1列每个位置上的最大值，为每个位置上是否有硬...
Give you the coins, and the total amount of money to change,find a solution for this chang...
引用：《背包问题——“01背包”最优方案总数分析及实现》及《背包问题——“完全背包”最优方案总数分析及实现》两篇文章
地址http://blog.csdn.net/wumuzi520/article/...
他的最新文章
讲师：汪剑
讲师：陈守元
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)本帖子已过去太久远了，不再提供回复功能。贪心算法解硬币找零问题
假如有一种货币，它有面值为1分、2分、5分和1角的硬币，最少需要多少个硬币来找出K分钱的零钱？
按照贪心算法的思想，需要不断地使用面值最大的硬币。如果要找零的值小于最大的硬币值，则尝试第二大的硬币，依次类推。
代码如下：
#define ONE 1
#define TWO 2
#define FIVE 5
#define TEN 10
int main()
int one=0,two=0,five=0,ten=0;
//尝试每一种硬币
while (money>=TEN)
money-=TEN;
while (money>=FIVE)
money-=FIVE;
while (money>=TWO)
money-=TWO;
while (money>=ONE)
money-=ONE;
//输出结果
cout<<"1角硬币数："<<ten<<
cout<<"5分硬币数："<<five<<
cout<<"2分硬币数："<<two<<
cout<<"1分硬币数："<<one<<
虽然贪心算法不是对所有问题都能得到整体的最优解，但是实际应用中的许多问题都可以使用贪心算法得到最优解。有时即使使用贪心算法不能得到问题的最优解，但最终结果也是较优的解