Project Euler——Problem 31

daybreakcx posted @ 2009年8月13日 06:17 in Prject Euler , 1358 阅读

原题与答案

Problem 31

22 November 2002

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

Answer:73682

分析与解答：

题目是说给定八种币值：1,2,5,10,20,50,100,200，问组成200一共有多少种可能。这是一个很经典的找钱问题，当然当钱币数量不多的时候可以搜索，直接枚举找到答案，但是有一种更好的方法，那就是利用动态规划来求解，首先我们得到动态规划方程： $\begin{displaymath}F[i][j]=\sum_{a[k]\leq j}{F[i-1][j-a[k]]}\end{displaymath}$ 。其中F[i][j]表示用前i种币值拼出j有多少种，那么就很容易可以理解那个方程了。当然我们注意到，新的F[i]总是依赖于F[i-1]的，因此我们可以从这个方面来考虑缩减空间消耗，可以利用滚动数组来实现，这样我们的空间消耗就是2*n了，同时我们看到由于对于j的值总是利用比j小的值求得，因此我们可以换一种思路，利用j求j后面的值，这样就又一次减少空间为一个一维数组了，初始化的时候我们设置得到0这个值有1种方法，具体的实现见程序源代码：

#include<stdio.h>
#include<string.h>
int coins[8]={1,2,5,10,20,50,100,200},cnt[201],i,j;
int main()
{
memset(cnt,0,sizeof(cnt));
cnt[0]=1;
for (i=0;i<8;i++)
for (j=0;coins[i]+j<=200;j++)
cnt[j+coins[i]]+=cnt[j];
printf("%d\n",cnt[200]);
return 0;
}