题目31：考察英国货币面值的组合问题

欧拉计划

Coin sums

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?

题目：

在英国，货币是由英镑 ￡，便士 p 构成的。一共有八种钱币在流通：

1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p) 和 ￡2 (200p).
要构造 ￡2 可以用如下方法：

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

允许使用任意数目的钱币，一共有多少种构造 ￡2 的方法？

lightninng

python版块的我来凑个热闹
1、解题思路：把问题由大划小，先想一个数用一种货币有多少种组合方法；在一种的基础上想两种货币怎么解决，可以想到，一种货币的数目固定了，另外一种的数目就固定了；在两种的基础上想三种，同理，两种的数目确定了便可以确定第三种的数目
基于此，递归函数解决的问题为，用n种不同的货币组成总钱数为m的方法的数目
例如，总数为200钱币，面值为100的钱币可以有三种选择方法，0,1,2，则在100的钱币为0，1，2的时候用剩下的面值的钱币分别组合成200,100,0即可
2、代码如下：

1. COUNT = 0  # 变量用于存储构造方法的数目
   
2. 
   
3. 
   
4. def coin_sums(pre_sum, coin_values, sum_value):
   
5.     global COUNT
   
6.     if len(coin_values) == 1:
   
7.         if sum_value % coin_values[0] == 0:
   
8.             COUNT += 1
   
9.             # print(pre_sum +
   
10.             #      "{0}*{1}p".format(sum_value//coin_values[0], str(coin_values[0])))
    
11.     else:
    
12.         for i in range(sum_value//coin_values[0] + 1):
    
13.             coin_sums(pre_sum + "{0}*{1}p + ".format(i, str(coin_values[0])),
    
14.                       coin_values[1:], sum_value-i*coin_values[0])
    
15. 
    
16. target = 200
    
17. coin_sums("{}p = ".format(str(target)),  [100, 50, 20, 10, 5, 2, 1], target)
    
18. print(COUNT)

复制代码

运行结果

1. >>> ================================ RESTART ================================
   
2. >>>
   
3. 73681
   
4. >>>

复制代码

jerryxjr1220

还缺1种，就是由2磅本身构成的。所以应该是
73682种

73682
[Finished in 5.5s]

1. count = 1
   
2. for a in range(3):
   
3.         if a * 100 <= 200:
   
4.                 for b in range(5):
   
5.                         if a * 100 + b *50 <= 200:
   
6.                                 for c in range(11):
   
7.                                         if a * 100 + b * 50 + c * 20 <= 200:
   
8.                                                 for d in range(21):
   
9.                                                         if a * 100 + b * 50 + c * 20 + d * 10 <= 200:
   
10.                                                                 for e in range(41):
    
11.                                                                         if a * 100 + b * 50 + c * 20 + d * 10 + e * 5 <= 200:
    
12.                                                                                 for f in range(101):
    
13.                                                                                         if a * 100 + b * 50 + c * 20 + d * 10 + e * 5 + f * 2 <= 200:
    
14.                                                                                                 for g in range(201):
    
15.                                                                                                         if a * 100 + b * 50 + c * 20 + d * 10 + e * 5 + f * 2 + g == 200:
    
16.                                                                                                                 count += 1
    
17. print (count)

复制代码

芒果加黄桃

1. # encoding:utf-8
   
2. # 英镑组合问题
   
3. from time import time
   
4. def euler031():
   
5.     count = 0
   
6.     for i in (0, 1):  # 1磅
   
7.         for j in (0, 1, 2, 3):  # 50便士
   
8.             if i * 100 + j * 50 > 200:
   
9.                 break
   
10.             for l in range(0, 10):  # 20便士
    
11.                 if i * 100 + j * 50 + l * 20 > 200:
    
12.                     break
    
13.                 for k in range(0, 20):  # 10便士
    
14.                     if i * 100 + j * 50 + l * 20 + k * 10 > 200:
    
15.                         break
    
16.                     for m in range(0, 40):  # 5便士
    
17.                         if i * 100 + j * 50 + l * 20 + k * 10 + m * 5 > 200:
    
18.                             break
    
19.                         for n in range(0, 100):  # 2便士
    
20.                             if i * 100 + j * 50 + l * 20 + k * 10 + m * 5 + n * 2 > 200:
    
21.                                 break
    
22.                             for o in range(0, 200):  # 1便士
    
23.                                 tmp = i * 100 + j * 50 + l * 20 + k * 10 + m * 5 + n * 2 + o
    
24.                                 if tmp == 200:
    
25.                                     count += 1
    
26.                                 # print(i, j, k, m, n, o)
    
27.                                     break
    
28.                                 if tmp > 200:
    
29.                                     break
    
30.     # 加上7种一种面值组成的  如果2磅也算的话  加8种
    
31.     print(count + 7)      
    
32. if __name__ == '__main__':
    
33.     start = time()
    
34.     euler031()
    
35.     print('cost %.6f sec' % (time() - start))
    

复制代码

73681
cost 1.730173 sec

渡风

此代码使用matlab编程
Problem31所用时间为2.0718秒
Problem31的答案为73682
感谢楼上的兄弟提供的思路

1. %% Problem31
   
2. % 题目31:考察英国货币面值的组合问题
   
3. %细节 Break的使用
   
4. function Output=Problem31(Input)
   
5. tic
   
6. if nargin==0
   
7. Input=200;
   
8. end
   
9. tic
   
10. Type=0;
    
11. for a1=0:Input
    
12.     for a2=0:100
    
13.         if a1+2*a2>Input
    
14.             break
    
15.         end
    
16.         for a3=0:40
    
17.             if a1+2*a2+5*a3>Input
    
18.                 break
    
19.             end
    
20.             for a4=0:20
    
21.                 if a1+2*a2+5*a3+10*a4>Input
    
22.                     break
    
23.                 end
    
24.                 for a5=0:10
    
25.                     if a1+2*a2+5*a3+10*a4+20*a5>Input
    
26.                         break
    
27.                     end
    
28.                     for a6=0:4
    
29.                         if a1+2*a2+5*a3+10*a4+20*a5+50*a6>Input
    
30.                             break
    
31.                         end
    
32.                         for a7=0:1
    
33.                             if a1+2*a2+5*a3+10*a4+20*a5+50*a6+100*a7==Input
    
34.                                 Type=Type+1;
    
35.                             end
    
36.                         end
    
37.                     end
    
38.                 end
    
39.             end
    
40.         end
    
41.     end
    
42. end
    
43. Type=2+Type;%一张200磅，两张100磅
    
44. Output=Type;
    
45. toc
    
46. toc
    
47. disp('此代码使用matlab编程')
    
48. disp(['Problem31所用时间为',num2str(toc),'秒'])
    
49. disp(['Problem31的答案为',num2str(Output)])
    

复制代码

由我们主宰

1. public class CoinSums{
   
2.         public static void main(String[] args){
   
3.                 int sum = 0,count = 1;
   
4.                 for(int hundred = 0;hundred <= 2;hundred++){
   
5.                         sum = 0;
   
6.                         sum = 100*hundred;
   
7.                         if(sum > 200){
   
8.                                 continue;
   
9.                         }
   
10.                         for(int fifty = 0;fifty <= 4;fifty++){
    
11.                                 sum = 100*hundred+50*fifty;
    
12.                                 if(sum > 200){
    
13.                                         continue;
    
14.                                 }
    
15.                                 for(int twenty = 0;twenty <= 10;twenty++){
    
16.                                         sum = 100*hundred+50*fifty+20*twenty;
    
17.                                         if(sum > 200){
    
18.                                                 continue;
    
19.                                         }
    
20.                                         for(int ten = 0;ten <= 20;ten++){
    
21.                                                 sum = 100*hundred+50*fifty+20*twenty+10*ten;
    
22.                                                 if(sum > 200){
    
23.                                                         continue;
    
24.                                                 }
    
25.                                                 for(int five = 0;five <= 40;five++){
    
26.                                                         sum = 100*hundred+50*fifty+20*twenty+10*ten+5*five;
    
27.                                                         if(sum > 200){
    
28.                                                                 continue;
    
29.                                                         }
    
30.                                                         for(int two = 0;two <= 100;two++){
    
31.                                                                 sum = 100*hundred+50*fifty+20*twenty+10*ten+5*five+2*two;
    
32.                                                                 if(sum > 200){
    
33.                                                                         continue;
    
34.                                                                 }
    
35.                                                                 for(int one = 0;one <= 200;one++){
    
36.                                                                         sum = 100*hundred+50*fifty+20*twenty+10*ten+5*five+2*two+one;
    
37.                                                                         if(sum == 200){
    
38.                                                                                 count ++;
    
39.                                                                                 System.out.print("第"+count+"种情况");
    
40.                                                                                 System.out.println(hundred+"\t"+fifty+"\t"+twenty+"\t"+ten+"\t"+five+"\t"+two+"\t"+one);
    
41.                                                                         }
    
42.                                                                 }
    
43.                                                         }
    
44.                                                 }
    
45.                                         }
    
46.                                 }
    
47.                         }
    
48.                 }
    
49.         }
    
50. }

复制代码

73682

王小召

73682

1. count = 0
   
2. 
   
3. 
   
4. def get_target(values, target):
   
5.     global count
   
6.     if len(values) > 1:
   
7.         for i in range(target//values[0] + 1):
   
8.             get_target(values[1:], target - i*values[0])
   
9.     else:
   
10.         count += 1
    
11.     return count
    
12. 
    
13. values = [200, 100, 50, 20, 10, 5, 2, 1]
    
14. target = 200
    
15. get_target(values, target)
    
16. print(count)

复制代码

debuggerzh

73682
动态规划之无限背包问题，状态转移方程为

                               
登录/注册后可看大图

1. #include<iostream>
   
2. #include<cmath>
   
3. #include<cstring>
   
4. using namespace std;
   
5. 
   
6. const int coin[] = {1,2,5,10,20,50,100,200};
   
7. int comb[10][205];
   
8. 
   
9. int dp(int i,int sum){
   
10.   //cout << i << " " << sum << endl;
    
11.   //if (sum == 0) {cnt++; return 0;}
    
12.   if (i == 1) return comb[i][sum] = 1;
    
13.   if (comb[i][sum] >= 0)  return comb[i][sum];
    
14.   int k = sum / coin[i-1];
    
15. 
    
16.   int res = 0;
    
17.   for (int j = 0;j <= k;j++)
    
18.     res += dp(i-1,sum - j*coin[i-1]);
    
19.   return comb[i][sum] = res;
    
20. }
    
21. 
    
22. int main(){
    
23.   memset(comb,-1,sizeof(comb));
    
24.   cout << dp(8,200) << endl;
    
25.   return 0;
    
26. }
    

复制代码

a1351468657

1. #include <stdio.h>
   
2. #include <time.h>
   
3. 
   
4. main()
   
5. {
   
6.         int sum, count = 0;
   
7.         int begin = time(0), end;
   
8. 
   
9.         for (int a = 0; a <= 2; a++)
   
10.         {
    
11.                 if (a == 2)
    
12.                 {
    
13.                         count++;
    
14.                         break;
    
15.                 }
    
16.                 for (int b = 0; b <= 4; b++)
    
17.                 {
    
18.                         for (int c = 0; c <= 10; c++)
    
19.                         {       
    
20.                                 for (int d = 0; d <= 20; d++)
    
21.                                 {
    
22.                                         for (int e = 0; e <= 40; e++)
    
23.                                         {       
    
24.                                                 for (int f = 0; f <= 100; f++)
    
25.                                                 {
    
26.                                                         for (int g = 0; g <= 200; g++)
    
27.                                                         {
    
28.                                                                 sum = a * 100 + b * 50 + c * 20 + d * 10 + e * 5 + f * 2 + g;
    
29.                                                                 if (200 == sum)
    
30.                                                                 {
    
31.                                                                         count++;
    
32.                                                                 }
    
33.                                                         }
    
34.                                                 }
    
35.                                         }
    
36.                                 }
    
37.                         }
    
38.                 }
    
39.         }
    
40.         end = time(0);
    
41.         printf("%d\n", count + 1);
    
42.         printf("time = %ds\n", end - begin);
    
43. }

复制代码

73682

guosl

1. /*
   
2. 动态规划
   
3. 答案：73682
   
4. */
   
5. #include <iostream>
   
6. using namespace std;
   
7. 
   
8. int a[8] = { 1, 2, 5, 10, 20, 50, 100,200 };//各种币值
   
9. long long f[201] = { 1 };//f[k]表示k值可以有多少种构造方式
   
10. 
    
11. int main(void)
    
12. {
    
13.   //动态转移方程
    
14.   for (int i = 0; i < 8; ++i)//对钞票的种类进行枚举
    
15.   {
    
16.     for (int j = 200; j >= a[i]; --j)//对要构造的值j进行枚举
    
17.     {
    
18.       for (int k = 1; k * a[i] <= j; ++k)//对构造的钞票张数进行枚举
    
19.         f[j] += f[j - k * a[i]];//在原来基础上添加k张值为a[i]便士的钞票
    
20.     }
    
21.   }
    
22.   cout << f[200] << endl;
    
23.   return 0;
    
24. }

复制代码