总共有以下几种币值:100元、50元、10元、5元、2元、1元,

用它们组成总额为10W元 有多少种组合?

推荐图书

  • 编程珠玑(第2版)


1个回答

C++ code:(思路写在注释里呢)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
using namespace std;

const int parValue[6] = {1,2,5,10,50,100};
long long dp[100000+1][6]; //dp[i][j]表示,使用最大面值不高于parValue[j]的钱币构成i元的方法数
/*
dp[0][j] = 1 , 0<=j<6
dp[i][j] = dp[i-parValue[j]][j]
           + dp[i-parValue[j-1]][j-1]  (if i>=parValue[j-1])
           + dp[i-parValue[j-2]][j-2]  (if i>=parValue[j-2])
           + ...
           + dp[i-parValue[0]][0]      (if i>=parValue[0])
*/

int main()
{
    for(int j=0;j<6;j++)
    {
        dp[0][j] = 1;
    }

    for(int i=1;i<=100000;i++)
    {
        for(int j=0;j<6;j++)
        {
            dp[i][j] = 0;
            for(int k=0;k<=j;k++)
            {
                if(i>=parValue[j-k])
                {
                    dp[i][j] += dp[i-parValue[k]][k];
                    assert(dp[i][j]>=0 && "overflow!");
                }
            }
        }
    }
    cout<< dp[100000][5] <<endl;
    system("pause");
}

Pascal code

procedure TForm1.Button1Click(Sender: TObject);
const
  N:integer=100000;
var
  i,j: Integer;
  k,count: Int64;
begin
  count:=0;
  for i:=0 to N div 10 do
  begin
    j:=(N div 10-i)div 5; k:=(j+4)*j div 4+1;
    inc(count,k*((5*i+4)*i+1));
  end;
  Memo1.Lines.Add(format(' %d元有%d种组合!',[N,count]));
end;

结果为: 100000元有167367668881914501种组合!