区块链技术博客
www.b2bchain.cn

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N的商品,请问最少他会收到多少硬币?的讲解

这篇文章主要介绍了Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N的商品,请问最少他会收到多少硬币?的讲解,通过具体代码讲解8434并且分析了Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N的商品,请问最少他会收到多少硬币?的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N的商品,请问最少他会收到多少硬币?的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=8434。具体如下:

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N的商品,请问最少他会收到多少硬币?

一、 直接数学公式解法
首先用最容易理解的办法,根据题目要求,直接硬性判断输出,设输入的N为购买的商品的价值,那么剩下的1024-N的金额就是我们需要判断能收到最少的硬币数量。
既然需要硬币数量最小,那么单个面值最大的硬币数量越多,最后总的硬币数量就会越少。所以,最简单的办法就是,先将64元硬币的最大数量求解出来,然后依次是16元、4元、1元。

方法1:

#include<iostream> #include<string> using namespace std; int main(){ 	int n; 	cin>>n; 	int cnum1,cnum2,cnum3,cnum4; 	cnum1=(1024-n)/64;                          //64元硬币的数量  	cnum2=((1024-n)%64)/16;                     //16元硬币的数量  	cnum3=(((1024-n)%64)%16)/4;                 //4元硬币的数量  	cnum4=(1024-n)-(cnum1*64+cnum2*16+cnum3*4); //1元硬币的数量 	cout<<cnum1+cnum2+cnum3+cnum4<<endl; 	return 0; } 

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N的商品,请问最少他会收到多少硬币?
可以看到提交是成功了,不过看起来还能继续优化。

二、采用动态规划的思路:

方法2:

  1. 利用背包问题进行参考,购买的物品价值为N,给定的面值选择的硬币种类选择为W,其额度是V ,剩余金额为M=1024-N;问应该如何选择硬币,使得到的硬币数量为最少??
  2. 将其转化为:令dp(j)表示在前j(1<=j<=W)个硬币中能够等于在i(1<=i<=V)的额度中的M的价值,则可以得到如下的动态规划函数:
    得到状态转移方程:
    (1) dp[0]=0
    (2) dp[j]=min(dp[j],dp[j-w[i]]+1) j<W
#include<iostream> #include<vector> #include<algorithm> #include<string> using namespace std;  int main() { 	int M,N; 	cin>>N; 	M=1024-N;                                 //购买后剩余的钱   	int dp[1024];                            //dp解法,类似背包问题,总的金额  	for(int i=1;i<=M;i++) 		dp[i]=100001; 	dp[0]=0;                                //初始为0  	int W[4]={1,4,16,64};                   //硬币种类  	for(int i=0;i<4;i++) 	{ 		for(int j=W[i];j<=M;j++) 		{ 			dp[j]=min(dp[j],dp[j-W[i]]+1);  //状态方程  		} 	} 	cout<<dp[M]<<endl; 	return 0; } 

本文地址https://www.b2bchain.cn/?p=8434

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N的商品,请问最少他会收到多少硬币?的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们