首页 > 其他 > 详细

凑硬币问题

时间:2017-12-11 19:41:12      阅读:293      评论:0      收藏:0      [点我收藏+]

最近开始学习动态规划,写个小题训练下:

假设有 1 元,3 元,5 元的硬币若干(无限),现在需要凑出 11 元,问如何组合才能使硬币的数量最少?

这个确实是最最基本的动态规划问题,注意这里我们不用贪心算法来解决,所以必须要引入状态和状态转移方程。

这个题的状态其实很简单,就是要凑出 i 元使用的最少的硬币数量,和题目要求的答案差不多的,只不过状态是对子问题的一种描述,动态规划最显著的特点就是问题和子问题近乎无差别的相似性,想解决最终问题,必须要先解决子问题。

状态转移方程实质就是一个不同状态间的关系表达式,类似于(或者说就是)数组的递推公式,表示了当前状态和前一个或者前几个状态间的关系,通过循环一步步筛选最后的最优解。

下面讲思路:假设 min[ i ]表示的是凑出 i 元需要的最少硬币数量,coin数组有3个元素,coin【0】=1,coin【1】=3,coin【2】=5,即三种硬币的面值,状态转移方程为:min【i】=Min(min【i-coin【k】】+ 1),其中k介于0到2之间

上代码:

 1 void main(){
 2         int min[12];
 3     min[0] = 0;    //初始边界值为0
 4     for (int i = 1; i < 12; i++)
 5         min[i] = 11;     //初始化最大值
 6     int coin[3] = {1,3,5};
 7     for (int i = 1; i <= 11; i++){
 8         for (int j = 0; j < 3; j++){
 9             if (coin[j] <= i&& min[i - coin[j]] + 1 < min[i]){
10                 min[i] = min[i - coin[j]] + 1;
11                 //cout << min[i] << endl;
12             }
13         }
14     }
15     for (int i = 1; i <= 11; i++){
16         cout << "" << i << "个硬币最小个数:" << min[i] << endl;
17     }
18 }

最后结果是3。

 

凑硬币问题

原文:http://www.cnblogs.com/messi2017/p/8024607.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!