题目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

#include<stdio.h>
#include<stdlib.h>
#define SIZE 100
#define VOLUME 50
#define BOUND (SIZE*(SIZE+1)*(SIZE*2+1)/6)
typedef struct node{
        int N;
        struct node* next;
}node;

typedef struct{
        node head;
        int bucket[BOUND];
}type;

static type sum[VOLUME];

void init(int *A)
{
        for(int i=1,j=1;i<=SIZE;i++){
                *A++=j;
                j+=i+i+1;
        }
}
int main()
{
        int N[SIZE];
        init(N);
        for(int i=0;i<SIZE;i++){
                for(int j=i>=VOLUME?VOLUME-1:i,k=i-VOLUME;j>=k&&j;j--){
                        node *p=sum[j-1].head.next;
                        while(p){
                                if(!(sum[j].bucket[p->N+N[i]])){
                                        node *tmp=malloc(sizeof *tmp);
                                        tmp->N=p->N+N[i];
                                        tmp->next=sum[j].head.next;
                                        sum[j].head.next=tmp;
                                }
                                sum[j].bucket[p->N+N[i]]+=sum[j-1].bucket[p->N];
                                p=p->next;
                        }
                }
                sum[0].bucket[N[i]]+=1;
                node *tmp=malloc(sizeof *tmp);
                tmp->N=N[i];
                tmp->next=sum[0].head.next;
                sum[0].head.next=tmp;
        }
        int total=0;
        for(int i=0;i<BOUND;i++){
                if(sum[VOLUME-1].bucket[i]==1)
                        total+=i;
        }
        printf("%d\n",total);

        return 0;
}

gunjang

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

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

fc1735

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

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

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