动态规划——最少硬币问题

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">       之前我在动态规划(dynamic programming)原理抛出了一个最少硬币问题。接下来,在这篇文章,我们将会对硬币问题进行一个全面的解析,并尽可能的解释动态规划的原理,希望读者们可以通过这个问题能初步了解DP。</span>

问题:最小硬币问题

描述:假设你有面值为1块、2块、5块的硬币,用尽可能少的硬币凑n块钱。假设n块钱是9块钱,相信你们想到的肯定是两张5块,两张2块,总共3张。然而当你的面值改为2块、3块、5块的硬币时候,大家都能看出来是一张5块,两张2块。那我们究竟解决这类问题呢?

分析:

1、对于这个硬币问题,我们每次都是取硬币,或者不取硬币。因此我们可以将这个硬币问题切割成若干个子问题(取不取这种硬币),而且每次决策都会用到这个子问题。而且所有的子问题中必定存在最优解。

2、每次取硬币,都仅仅是做出决策,判断是否取这三种硬币,每次决策之后,除了n块钱会改变之外,其他都没有改变,都是判断是否取这三种硬币的一种,因此可以说硬币问题无后效性。

我们再回想一下实现动态规划的前提

(1)、最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

(2)、无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关;

(3)、有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)。

看了描述硬币问题似乎可以用动态规划解决喔!

根据我们之前分析:我们推出这个动态规划问题的状态转移方程为:

然后根据公式我们生成这么一个表格

       如果读者对这个表有不懂的话,可以看看下面的解析,相信就会理解怎么做的了,已经看懂的可以直接跳过。

       首先,蓝色区域代表需要兑换的面值大小,绿色区域代表的是当前所拥有的面值类型(假设当前有2块、3块、5块),而黄色区域则表示使用当前面值的硬币能不能将指定的money找开,另外为了保证能够让电脑知道是找开了,我们还需要一个辅助变量maxCoin,这个是记录当前面值全部兑换成1块钱所需要的硬币数目。

      在每次操作之前我们先把当前的F(i)置零以及将valueCoin置零,果发现调用F(i)公式时候所需要的硬币数目变少了,那么我们就更新minCoin和valueCoin。

      第二!因为硬币大小是我们自定义的,所以有部分钱我们是找不开的!!比如说0块钱,1块钱,压根就不能用2块、3块、5块找开,所以这里面我们要使用valueCoin记录当前是否可以找开,如果不能找开,valueCoin不会改变,否则就改变成能兑换成的最大的value。(valueCoin是为了到时候我们要输出硬币数目的时候用的)

下面我们对这个状态转移方程举个例子吧,(感谢tubby_ting纠正数据的错误)

money[i]=2,value[j]=2的时候,因为money[i]>=velue[j]所以:

f(2)=f(2-2)+1 = 1

valueCoin[2]=2

money[i]=7,value[j]=2:

F(7)= f(7-2)+1 = f(5)+1=2

valueCoin[7]=2

money[i]=7,value[j]=3:

F(7)= f(7-3)+1 = f(4)+1=3

valueCoin[7]不作改变

money[i]=7,value[j]=5:

F(7)= f(7-5)+1 = f(2)+1=3

valueCoin[7]=5

        如果上面的推理看得懂的话,那么相信大家已经可以将代码大致的写出来的了,由于时间关系,代码我会在接下来有空的时间补上,因为之前的状态转移方程写错了,写成了01背包问题的方程了,导致整个文章推倒重写。

大哭

       文章到了最后说说自己的感受把:我觉得动态规划是一种既让人爱又让人恨的算法吧,为什么?因为有时候你看到一个问题,你会想到有可能用贪心,后来发现贪心不行,有可能是DP。好了,你知道是DP了,居然不知道这个问题的状态转移方程,找到一个可能的状态转移方程了,发现居然有部分是错误的…心塞无比,所以说,DP这个东西,对于我们这些初学者来说,真的是一个很磨人的东西!

#include <iostream>using namespace std;int find_dest(int money, int *coin, int n){	int * minCoin = new int[money + 1]();	int * valueCoin = new int[money + 1]();	memset(minCoin, 0, sizeof(int)*(money + 1));	memset(valueCoin, 0, sizeof(int)*(money + 1));	for (int i = 1; i <= money; i++)	{		int maxCoin = i;		int value = 0;		for (int j = 0; j < n; j++)		{			if (i >= coin[j])			{				if (minCoin[i - coin[j]] + 1 <= maxCoin && (i==coin[j]||valueCoin[i - coin[j]] != 0)/*检测上一个是否有效,无效则跳过*/)				{					maxCoin = minCoin[i - coin[j]] + 1;//F[I] = MIN{F[I-VALUE[J]]+1}					value = coin[j];				}			}		}		minCoin[i] = maxCoin;		valueCoin[i] = value;	}	if (valueCoin[money] != 0)	{		while (money)		{			cout << valueCoin[money] << ",";			money -= valueCoin[money];		}		cout << endl;	}	else	{		cout << "error!" << endl;	}	delete[] minCoin;	delete[] valueCoin;	return 0;}int main(){	int money = 9;	int coin[3] = { 2, 3, 5 };	find_dest(money, coin, 3);	system("pause");	return 0;}

点这里可以跳转到人工智能网站