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

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; } 

可以看到提交是成功了，不过看起来还能继续优化。

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

方法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; }