硬币找钱问题-程序员宅基地

硬币找钱问题

Time Limit:1000MS  Memory Limit:65536K
Total Submit:3 Accepted:1

Description

设有6 种不同面值的硬币,各硬币的面值分别为5 分,1 角,2 角,5 角,1 元,2元。现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组Coins[1:6]中,商店里各面值的硬币有足够多。在1次购物中希望使用最少硬币个数。例如,1 次购物需要付款0.55 元,没有5 角的硬币,只好用2*20+10+5 共4 枚硬币来付款。如果付出1 元,找回4 角5 分,同样需要4 枚硬币。但是如果付出1.05 元(1 枚1元和1 枚5分),找回5 角,只需要3 枚硬币。这个方案用的硬币个数最少。

对于给定的各种面值的硬币个数和付款金额,计算使用硬币个数最少的交易方案。

Input

输入数据有若干组,每一行有6 个整数和1 个有2 位小数的实数。分别表示可以使用的各种面值的硬币个数和付款金额。文件以6 个0 结束。

Output

将计算出的最少硬币个数输出。结果应分行输出,每行一个数据。如果不可能完成交易,则输出“impossible”。

Sample Input

2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55
0 0 0 0 0 0

 

Sample Output

2
3

 

Source :《算法设计与分析》

 
解题思路:01背包,完全背包
change[i]表示商店支付面值为i需要的最少硬币个数;
dp[i]表示顾客现有的硬币数支付面值为i需要的最少硬币数;
w为当前要支付的实际面值,若顾客支付面值为k的钱(k>=w),商家找钱k-w,该条件下最少需要的硬币数为dp[k]+change[k-w],
由此推得,最少硬币数为所有符合条件k>=w下最小的dp[k]+change[k-w];
即: ans = min(dp[k]+change[k-w])(k>=w)

对于change[i],商店里各面值的硬币有足够多,故可用完全背包实现
对于dp[i],可用混合背包计算,这里我直接拆成01背包来实现(比较暴力,O(∩_∩)O~)。
PS:为减少空间开销,最终化为以5分为单位计算

    其实,这个算法在时间和空间上的牺牲还是比较大的,可用贪心进行优化,可惜当年没深入去想……

代码
#include < stdio.h >
#include
< string .h >

const int N = 20000 ;
int change[N]; // change[i]为面值为i的钱至少需要的硬币个数
int dp[N]; // dp[i]为当前拥有的硬币数量条件下表示面值为i的最少硬币个数
int value[ 6 ] = { 1 , 2 , 4 , 10 , 20 , 40 }; // 每种硬币对应面值,依次为1,2,4,10,20,40个五分,即5,10,20,50,100,200;
int number[ 6 ]; // 对应于当前拥有的每种硬币个数

void init() // 计算change[i]
{
int i,j;
for (i = 0 ;i < N;i ++ )change[i] =- 1 ;
change[
0 ] = 0 ;
for (i = 0 ;i < 6 ;i ++ )
{
for (j = value[i];j < N;j ++ ) // 这里使用完全背包,不能理解的话可参考背包九讲
{
if (change[j - value[i]] !=- 1 )
{
int temp = change[j - value[i]] + 1 ;
if (change[j] ==- 1 || temp < change[j])change[j] = temp;
}
}
}
}
int main()
{
// freopen("change.in","r",stdin);

init();
// 计算出change[i]

while (scanf( " %d%d%d%d%d%d " , & number[ 0 ], & number[ 1 ], & number[ 2 ], & number[ 3 ], & number[ 4 ], & number[ 5 ]) != EOF)
{
int sum = 0 ;
int kk;
for (kk = 0 ;kk < 6 ;kk ++ )sum += number[kk];
if (sum == 0 ) break ;
double weight;
scanf(
" %lf " , & weight);
weight
= weight * 100 ;
// printf("weight = %lf\n",weight);
int w = int (weight + 0.0000001 ); // 处理精度问题
// printf("%d\n",w);

if (w % 5 != 0 ) // 若不能整除,则无法表示
{
printf(
" impossible\n " );
continue ;
}
else
w
= w / 5 ;

int i,j;
memset(dp,
- 1 , sizeof (dp));
dp[
0 ] = 0 ;
int bigger = 0 ;
for (i = 0 ;i < 6 ;i ++ )//计算顾客支付面值i需要的最少硬币数dp[i]
{
while (number[i] -- ) //将混合背包拆成01背包做,写水了点。。。
{
bigger
= bigger + value[i];
for (j = bigger;j >= value[i];j -- )
{
if (dp[j - value[i]] !=- 1 )
{
int temp = dp[j - value[i]] + 1 ;
if (dp[j] ==- 1 || temp < dp[j])
{
dp[j]
= temp;
}
}
}
}
}

int ans =- 1 ;
for (i = w;i <= bigger;i ++ )//寻找最少硬币组合
{
if (dp[i] !=- 1 )
{
int need = i - w;
if (change[need] !=- 1 )
{
int temp = dp[i] + change[need];
if (ans ==- 1 || ans > temp)ans = temp;
}
}
}

// for(i=0;i<N;i++)
// if(dp[i]!=-1)
// printf("dp[%d]=%d\n",i,dp[i]);

if (ans !=- 1 )
printf(
" %d\n " ,ans);
else
printf(
" impossible\n " );
}
return 0 ;
}

 

转载于:https://www.cnblogs.com/AndreMouche/archive/2010/12/25/1916584.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/a48634331/article/details/102206837

智能推荐

Centos 7 下使用 iftop 监控流量_centos7查看实时下载流量-程序员宅基地

文章浏览阅读329次。Centos 7 下使用 iftop 监控流量Centos 7 下使用 iftop 监控流量下载安装参考链接Centos 7 下使用 iftop 监控流量你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。下载安装我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了如下几点新功能,帮助你用它写博客:链接: 下载 iftop_centos7查看实时下载流量

C#接口_c# 接口 casting-程序员宅基地

文章浏览阅读2.7k次,点赞3次,收藏11次。C#接口++++接口: 接口是一组包含了类或结构可以实现的功能的定义。++++以上例子我们可以定义接口IFly 和ISpeak,某个类实现了这两个接口,则该类便具有了飞和说话的功能。 没实现接口则不具备对应的功能。++++由于C#只支持单继承,所以接口支持多实现的特性可以在一定程度上弥补该不足。++++我们可以通过interface关键字定义接口:interfa_c# 接口 casting

Oracle之DBMS_CRYPTO包的使用(加密包)_dbms_crypto.encrypt-程序员宅基地

文章浏览阅读8.7k次。关于加密的内容比较较多,我这里主要介绍使用DBMS_CRYPTO进行对数据的加密以及加密后的数据进行解密。下面我们以例子的形式进行说明。如果要使用dbms_crypto包,需要授予如下权限:SQL&gt; grant execute on dbms_crypto to djp012 /Grant succeeded.SQL&gt;下面,我们看一个数据加密的例子:SQL&gt; se..._dbms_crypto.encrypt

deepin 为什么没有gedit命令_gedit:找不到命令-程序员宅基地

文章浏览阅读2k次。最近为了在办公的时候也能搞搞linux 特意买了个linux笔记本 华为都装的是deepin这个系统这个系统是没有gedit命令的edit是一个GNOME桌面环境下兼容UTF-8的文本编辑器。它使用GTK+编写而成,因此它十分的简单易用,有良好的语法高亮,对中文支持很好,支持包括gb2312、gbk在内的多种字符编码。gedit是一个自由软件。这是 Linux 下的一个纯文本编辑器,但你也可以把它用来当成是一个集成开发环境 (IDE), 它会根据不同的语言高亮显现关键字和标识符。 [1]而在d_gedit:找不到命令

CStatic的自绘_cstatic 自绘-程序员宅基地

文章浏览阅读976次。静态控件也是比较常用的控件,在VS开发环境中用的应该挺频繁的吧。其实mfc中实现对窗口美化,主要依赖于重绘。static控件也是个窗口,windows为其留有自绘的权利,可以设置其样式为SS_OWNERDRAW,Windows就会把其绘制权利交给我们的代码,怎么绘制就看我们的代码了。mfc中更好的一种方式就是消息反射,省的自己来做这一步操作了,我们重载CStatic中的DrawItem方法_cstatic 自绘

C语言-将数组A中的内容和数组B中的内容进行交换。(数组一样大)_c语言数组将数组a中的数传给数组b-程序员宅基地

文章浏览阅读477次。实现方法:先把数组a的值循环赋值给数组c;数组b的值循环赋值给a;数组c的值赋值给b;#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>#include<stdlib.h>int main(){ int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int b[1..._c语言数组将数组a中的数传给数组b

随便推点

GridView使用示例(三)_gridview 示例-程序员宅基地

文章浏览阅读1.7k次。main.xml如下:

python获取gitlab日志信息_git action info_refs-程序员宅基地

文章浏览阅读5.6k次,点赞3次,收藏17次。利用python记录所有git用户的远程操作(推送、同步)_git action info_refs

MFC 读取 配置文件_mfc配置文件的读写-程序员宅基地

文章浏览阅读1.2k次。MFC 读取 配置文件 CString iniFilePath = this->str_module_directory + _T("\\config.ini"); DWORD ret; FILE * fp = fopen((CT2A)(iniFilePath), "r"); CString returnString; TCHAR szValue[MAX_PATH + 1] = _T(""); if (fp) { ret = GetPrivateProfileString(__mfc配置文件的读写

java两数组相加(合并)_java 数组相加-程序员宅基地

文章浏览阅读3.1k次,点赞2次,收藏6次。java两数组相加(合并)_java 数组相加

python怎么打中文mac版-帮你解决mac上python没法输入中文问题-程序员宅基地

文章浏览阅读436次。我是做互联网运营的,但是想跨点界,学点代码来提高工作效率。经过咨询,做技术的同事推荐学习python。我执行力杠杠的哈,找了个网络课程,教python入门,根据老师的介绍去网站:http://www.python.org/,安装好了python(3.6.1),打开idle,上面有几行红色的字,刚开始没太注意,因为能输入英文。第二天上课,要输入中文,结果怎么都输入不进中文,输入法切换了好几遍都没有用..._macos pythen 系统语言设置中文

hibernate3.4+struts1.3分页封装,有兴趣者可以看一下-程序员宅基地

文章浏览阅读62次。Hibernate3.4+struts1.3分页的封装环境:hibernate3.4 +struts1.3 +jspPage.javapackage com.nongxue.util;public class Page { private int totalPage;//总页数 private int curPage;//当前页数 public static int...