动态规划算法求解硬币找零问题

moqihuf · 发表于 2012-7-25 01:28

动态规划的基本思想是将待求解问题分解成若干个子问题，先求解子问题，并将这些子问题的解保存起来，如果以后在求解较大子问题的时候需要用到这些子问题的解，就可以直接取出这些已经计算过的解而免去重复运算。保存子问题的解可以使用填表方式，例如保存在数组中。
用一个实际例子来体现动态规划的算法思想——硬币找零问题。
硬币找零问题描述：现存在一堆面值为 V1、V2、V3 … 个单位的硬币，问最少需要多少个硬币才能找出总值为 T 个单位的零钱？假设这一堆面值分别为 1、2、5、21、25 元，需要找出总值 T 为 63 元的零钱。
很明显，只要拿出 3 个 21 元的硬币就凑够了 63 元了。
基于上述动态规划的思想，我们可以从 1 元开始计算出最少需要几个硬币，然后再求 2 元、3元…每一次求得的结果都保存在一个数组中，以后需要用到时则直接取出即可。那么我们什么时候需要这些子问题的解呢？如何体现出由子问题的解得到较大问题的解呢？
其实，在我们从 1 元开始依次找零时，可以尝试一下当前要找零的面值（这里指 1 元）是否能够被分解成另一个已求解的面值的找零需要的硬币个数再加上这一堆硬币中的某个面值之和，如果这样分解之后最终的硬币数是最少的，那么问题就得到答案了。
单是上面的文字描述太抽象，先假定以下变量：
values[] : 保存每一种硬币的币值的数组
valueKinds :币值不同的硬币种类数量，即values[]数组的大小
money : 需要找零的面值
coiUsed[] : 保存面值为 i 的纸币找零所需的最小硬币数
算法描述：
当求解总面值为 i 的找零最少硬币数 coiUsed[ i ] 时，将其分解成求解 coiUsed[ i – cents]和一个面值为 cents 元的硬币，由于 i – cents < i ，其解 coiUsed[ i – cents] 已经存在，如果面值为 cents 的硬币满足题意，那么最终解 coiUsed[ i ] 则等于 coiUsed[ i – cents] 再加上 1（即面值为 cents）的这一个硬币。
下面用代码实现并测试一下：
public class CoiChange {
/**
* 硬币找零：动态规划算法
*
* @param values
*  :保存每一种硬币的币值的数组
* @param valueKinds
*  :币值不同的硬币种类数量，即coinValue[]数组的大小
* @param money
*  :需要找零的面值
* @param coiUsed
*  :保存面值为i的纸币找零所需的最小硬币数
*/
public static void makeChange(int[] values, int valueKinds, int money,
int[] coiUsed) {
coiUsed[0] = 0;
// 对每一分钱都找零，即保存子问题的解以备用，即填表
for (int cents = 1; cents <= money; cents++) {
// 当用最小币值的硬币找零时，所需硬币数量最多
int minCoi = cents;
// 遍历每一种面值的硬币，看是否可作为找零的其中之一
for (int kind = 0; kind < valueKinds; kind++) {
// 若当前面值的硬币小于当前的cents则分解问题并查表
if (values[kind] <= cents) {
int temp = coiUsed[cents - values[kind]] + 1;
if (temp < minCoi) {
   minCoi = temp;
}
}
}
// 保存最小硬币数
coiUsed[cents] = minCoi;
System.out.println("面值为 " + (cents) + " 的最小硬币数 : "
+ coiUsed[cents]);
}
}
public static void main(String[] args) {
// 硬币面值预先已经按降序排列
int[] coinValue = new int[] { 25, 21, 10, 5, 1 };
// 需要找零的面值
int money = 63;
// 保存每一个面值找零所需的最小硬币数，0号单元舍弃不用，所以要多加1
int[] coiUsed = new int[money + 1];
makeChange(coinValue, coinValue.length, money, coiUsed);
}
}
测试结果：
面值为 1 的最小硬币数 : 1  面值为 2 的最小硬币数 : 2  面值为 3 的最小硬币数 : 3  面值为 4 的最小硬币数 : 4  面值为 5 的最小硬币数 : 1  面值为 6 的最小硬币数 : 2  ...  ...  面值为 60 的最小硬币数 : 3  面值为 61 的最小硬币数 : 4  面值为 62 的最小硬币数 : 4  面值为 63 的最小硬币数 : 3
   上面的代码并没有给出具体应该是哪几个面值的硬币，这个可以再使用一些数组保存而打印出来。
参考lovebeyond19831993.blog.163.com/blog/static/131811444201101901819833/
问题：
假设有n种面值不同的硬币，个个面值存于数组T[1:n]中，现在用这些硬币来找钱，各种硬币的使用个数不限;
求对于给定的钱数N，最少可以由几枚硬币组成，并输出硬币序列。
分析：
假设对于i = 1...N-1，所需最少的硬币数Count(i) 已知，那么对于N，所需的硬币数为Min( Count(i) + Count(N-i)) , i=1...N-1;
于是一个直观的方法是用递归计算。
但是，递归过程中，每次计算Count(i)，都会重复计算 Count(1)....Count(i-1); 这样时间复杂度就是O(N2);
事实上，这是一个典型的动态规划问题，我们可以从1开始记录下每个钱数所需的硬币枚数，避免重复计算，为了能够输出硬币序列，我们还需要记录下每次新加入的硬币。
下面给出用动态规划解决此问题的递推式：
参数说明：当只用面值为T[1],T[2],…T[n]来找出钱j时，所用的硬币的最小个数记为C(i,j),则C(i,j)的递推方程为：
算法设计：
#include <iostream>
using namespace std;
int min_number_of_stamps(cot int* array, size_t array_size, int request) {
if (array == NULL || array_size <= 0 || request < 1) {
return -1;
}
int* numofStamps = new int[request + 1];
numofStamps[0] = 0;
for(int i = 1; i <= request; i++){
int cn = i;
for(size_t j = 0; j < array_size; j++){
   if(array[j] <= i){
int tmp = numofStamps[i - array[j]] + 1;
if(tmp < cn)
cn = tmp;
   }
}
numofStamps[i] = cn;
}
   int t = numofStamps[request];
delete[] numofStamps;
return t;
}
int main() {
int array[] = { 90, 30, 24, 15, 12, 10, 5, 3, 2, 1 };
int array_size = sizeof(array) / sizeof(int);
int t = min_number_of_stamps(array, array_size, 32);
cout << t << endl;
}

kaey8686 · 发表于 2012-7-31 09:48

kaey8686 · 发表于 2012-7-31 09:52

账号		自动登录	找回密码
密码			注册