题目201：总和唯一的子集

欧拉计划

Subsets with a unique sum

For any set A of numbers, let sum(A) be the sum of the elements of A.
Consider the set B = {1,3,6,8,10,11}.
There are 20 subsets of B containing three elements, and their sums are:

  

Some of these sums occur more than once, others are unique.
For a set A, let U(A,k) be the set of unique sums of k-element subsets of A, in our example we find U(B,3) = {10,12,14,18,21,25,27,29} and sum(U(B,3)) = 156.

Now consider the 100-element set S = {1², 2², ... , 100²}.
S has 100891344545564193334812497256 50-element subsets.

Determine the sum of all integers which are the sum of exactly one of the 50-element subsets of S, i.e. find sum(U(S,50)).

题目：

对于数字组成的任意集体 A，定义 sum(A) 为 A 中元素的和。

考虑集合 B = {1,3,6,8,10,11}

B 中包含三个元素的子集共有 20 个，他们的和分别是：

  

某些和值出现不只一次，其它的则是唯一的。

对于集合 A，定义 U(A,k) 为 A 中 k 个元素子集的唯一和值的集合。在上例中，我们得到 U(B,3) = {10,12,14,18,21,25,27,29} ，而 sum(U(B,3)) = 156。

现在考虑有一百个元素的集合 S = {1², 2², ... , 100²}。

它的包含 50 个元素的子集总共有 100891344545564193334812497256 个。

请对上面那 100891344545564193334812497256 个集合，找出它们唯一和的集合 U(S,50)，求 sum(U(S,50))。

fc1735

brute force

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #define SIZE 100
   
4. #define VOLUME 50
   
5. #define BOUND (SIZE*(SIZE+1)*(SIZE*2+1)/6)
   
6. typedef struct node{
   
7.         int N;
   
8.         struct node* next;
   
9. }node;
   
10. 
    
11. typedef struct{
    
12.         node head;
    
13.         int bucket[BOUND];
    
14. }type;
    
15. 
    
16. static type sum[VOLUME];
    
17. 
    
18. void init(int *A)
    
19. {
    
20.         for(int i=1,j=1;i<=SIZE;i++){
    
21.                 *A++=j;
    
22.                 j+=i+i+1;
    
23.         }
    
24. }
    
25. int main()
    
26. {
    
27.         int N[SIZE];
    
28.         init(N);
    
29.         for(int i=0;i<SIZE;i++){
    
30.                 for(int j=i>=VOLUME?VOLUME-1:i,k=i-VOLUME;j>=k&&j;j--){
    
31.                         node *p=sum[j-1].head.next;
    
32.                         while(p){
    
33.                                 if(!(sum[j].bucket[p->N+N[i]])){
    
34.                                         node *tmp=malloc(sizeof *tmp);
    
35.                                         tmp->N=p->N+N[i];
    
36.                                         tmp->next=sum[j].head.next;
    
37.                                         sum[j].head.next=tmp;
    
38.                                 }
    
39.                                 sum[j].bucket[p->N+N[i]]+=sum[j-1].bucket[p->N];
    
40.                                 p=p->next;
    
41.                         }
    
42.                 }
    
43.                 sum[0].bucket[N[i]]+=1;
    
44.                 node *tmp=malloc(sizeof *tmp);
    
45.                 tmp->N=N[i];
    
46.                 tmp->next=sum[0].head.next;
    
47.                 sum[0].head.next=tmp;
    
48.         }
    
49.         int total=0;
    
50.         for(int i=0;i<BOUND;i++){
    
51.                 if(sum[VOLUME-1].bucket[i]==1)
    
52.                         total+=i;
    
53.         }
    
54.         printf("%d\n",total);
    
55. 
    
56.         return 0;
    
57. }
    

复制代码

gunjang

fc1735 发表于 2018-7-31 23:00
brute force

弱弱问下，有生之年这个程序能运行完吗？

fc1735

gunjang 发表于 2019-8-11 21:30
弱弱问下，有生之年这个程序能运行完吗？

1. S = map(lambda x: x**2, range(1, 101))
   
2. U = list(map(lambda x: {}, range(51)))
   
3. U[0][0] = 1
   
4. for i in S:
   
5.   for j in reversed(range(50)):
   
6.     for k in U[j]:
   
7.       U[j+1][k+i] = U[j+1].get(k+i, 0) + U[j][k]
   
8. print(sum(map(lambda x: x[0], filter(lambda x: x[1] == 1, U[50].items()))))

复制代码

用python写的, 大约要跑2分钟, 不用dict的话可以1秒跑完