Project Euler——Problem 31 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 30
Project Euler——Problem 32

Project Euler——Problem 31

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

原题与答案

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种方法,具体的实现见程序源代码:

 

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

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter