文档章节

c++动态规划解决硬币换零钱的问题

元禛慎独
 元禛慎独
发布于 2017/02/09 10:06
字数 289
阅读 203
收藏 0

使用3枚币值分别为  1、3、4的硬币兑换11,最少需要几枚硬币。注意此题属于恰好装满的情况,需注意初始化,数组F(0)为0,其余的为正极大值或极小值(具体是极大还是极小,视状态转移方程中取的是min还是max)

#include <iostream>
#include <cstdlib>

using std::cout;
using std::endl;

int arr_coin[3]={1,3,4};
int n=11;
int arr_c[4][12];

void init()
{
    for(int i=0;i<4;++i)
      for(int j=0;j<n+1;++j)
        arr_c[i][j]=9999;
     for(int i=0;i<4;++i)
      arr_c[i][0]=0;
}

int charge()
{
    for(int j=1;j<=n;++j)
    {
        for(int i=1;i<=3;++i)
        {
            if(j<arr_coin[i-1])
            {
                arr_c[i][j]=arr_c[i-1][j];
            }
            arr_c[i][j]=std::min(arr_c[i-1][j], arr_c[i][j-arr_coin[i-1]]+1);
        }
    }
    return arr_c[3][n];
}

int main(int argc, char** argv)
{
    std::system("clear");
    init();
    for(int i=0;i<4;++i)
    {
      for(int j=0;j<n+1;++j)
        cout << arr_c[i][j] << " ";
    cout << endl;
    }
    cout << endl;
    cout << charge() << endl;
}
########################

输出:

0 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 
0 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 
0 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 
0 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 

3
 

© 著作权归作者所有

元禛慎独
粉丝 3
博文 209
码字总数 60366
作品 0
朝阳
程序员
私信 提问
动态规划算法思想解决找零钱问题

动态规划算法思想解决找零钱问题 前言 关于找零钱问题,网上已经有很多相关的资料以及优秀的文章博客等。这里写这篇博客的初衷很简单,就是为了方便自己,回过头来捡起这个知识能快一点,接受...

niaonao
2017/10/16
0
0
动态规划之硬币表示问题

问题描述: 有数量不限的硬币,币值为25分、10分、5分和1分,请编写代码计算n分有几种表示法。 求解思路: 这也是典型的动态规划问题,我们可以这样考虑:当只有1分的硬币时,n从1到n分别有多...

一贱书生
2016/11/22
77
0
C语言编程学习之找零钱的贪婪算法

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/05/14
0
0
程序算法与人生选择,算法决定选择,选择决定人生,你的算法呢?

程序算法与人生选择 每年一到要找工作的时候,怎么选offer,去腾讯还是去豆瓣,去外企还是去国内的企业,去创业还是去考研,去北京还是回老家,该不该去创新工场?该不该去thoughtworks?……...

这个人很懒什么都没留下
2018/07/24
0
0
详解动态规划最少硬币找零问题--JavaScript实现

硬币找零问题是动态规划的一个经典问题,其中最少硬币找零是一个变种,本篇将参照上一篇01背包问题的解题思路,来详细讲解一下最少硬币找零问题。如果你需要查看上一篇,可以点击下面链接: ...

YinTokey
2018/05/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

MongoDB系列-解决面试中可能遇到的MongoDB复制集(replica set)问题

关注我,可以获取最新知识、经典面试题以及微服务技术分享   MongoDB复制集(replica set):MongoDB复制集维护相同数据集的一组mongod进程,复制集是生产部署的基础,具有数据冗余以及高可用...

ccww_
42分钟前
4
0
SpringBoot系列:Spring Boot集成Spring Cache,使用RedisCache

前面的章节,讲解了Spring Boot集成Spring Cache,Spring Cache已经完成了多种Cache的实现,包括EhCache、RedisCache、ConcurrentMapCache等。 这一节我们来看看Spring Cache使用RedisCache。...

杨小格子
51分钟前
3
0
OpenJDK之CountDownLatch

OpenJDK8,本人看的是openJDK。以前就看过,只是经常忘记,所以记录下 图1 CountDownLatch是Doug Lea在JDK1.5中引入的,作用就不详细描述了, await()方法,如果还有线程在执行,那么当前线程...

克虏伯
57分钟前
4
0
简单编程

1.编写一个程序,提示用户输入名和姓,然后以“名,姓”的格式打印出来。 #include<stdio.h>int main(){char name[3];char family[3];printf("Please input your name and family:\n...

电子工程197沈志初
今天
4
0
详解Mysql分布式事务XA(跨数据库事务)

在开发中,为了降低单点压力,通常会根据业务情况进行分表分库,将表分布在不同的库中(库可能分布在不同的机器上)。在这种场景下,事务的提交会变得相对复杂,因为多个节点(库)的存在,可...

slagga
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部