Pascal编程 把100元钞票换成50元、20元和10元的小钞票，共有多少种方案，输出每一种兑换方案

Question

free Pascal

Answer 1

本题等效于将10元钱用5元，2元，1元如何组成。

var m,m5,m2,m1:integer;
 
begin
    readln(m); //输入总钱数
    writeln('5Y':5,'2Y':5,'1Y':5);
    writeln('-----------------------');
    for m5:=0 to (m div 5) do  //5元最多张数为 m div5
       for m2:=0 to ((m-m5*5) div 2) do  //从剩余钱数里计算2元最多张数
          begin
           m1:=m-m5*5-m2*2; //扣除5元，2元的钱数以后就是1元的张数
           writeln(m5:5,m2:5,m1:5);
          end;
end.

输入10元：

如果不允许0张出现，那么程序修改如下：

var m,m5,m2,m1:integer;
 
begin
    readln(m); //输入总钱数
    writeln('5Y':5,'2Y':5,'1Y':5);
    writeln('-----------------------');
    for m5:=1 to (m div 5) do  //5元最多张数为 m div5
       for m2:=1 to ((m-m5*5) div 2) do  //从剩余钱数里计算2元最多张数
          begin
             m1:=m-m5*5-m2*2; //扣除5元，2元的钱数以后就是1元的张数
             if m1>0 then writeln(m5:5,m2:5,m1:5);
          end;
end.

 

Answer 2

可以用动态规划的思想，将问题拆分成若干子问题

定义状态f[i]表示用题中3种纸币兑换i元的方案总数，则有

f[i]=∑(f[i-j]); 其中j为50、20、10，边界为f[0]~f[9]为0；

又因为题中所有数据均为10的整倍数，可以同时除以10，再进行以上DP，则范围缩小10倍，也可以省去很多无效枚举（如24、33之类非整10的数），此时的边界为f[0]=0；

这个是1维的，不知道符不符合LZ的要求……
临时想的算法，没有严格验证正确性，如有问题，请追问，谢谢。