题目201：总和唯一的子集
Subsets with a unique sumFor 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 = {12, 22, ... , 1002}.
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 = {12, 22, ... , 1002}。
它的包含 50 个元素的子集总共有 100891344545564193334812497256 个。
请对上面那 100891344545564193334812497256 个集合，找出它们唯一和的集合 U(S,50)，求 sum(U(S,50))。
本帖最后由 fc1735 于 2018-7-31 23:05 编辑
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;
}type;
static type sum;
void init(int *A)
{
for(int i=1,j=1;i<=SIZE;i++){
*A++=j;
j+=i+i+1;
}
}
int main()
{
int N;
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.head.next;
while(p){
if(!(sum.bucket])){
node *tmp=malloc(sizeof *tmp);
tmp->N=p->N+N;
tmp->next=sum.head.next;
sum.head.next=tmp;
}
sum.bucket]+=sum.bucket;
p=p->next;
}
}
sum.bucket]+=1;
node *tmp=malloc(sizeof *tmp);
tmp->N=N;
tmp->next=sum.head.next;
sum.head.next=tmp;
}
int total=0;
for(int i=0;i<BOUND;i++){
if(sum.bucket==1)
total+=i;
}
printf("%d\n",total);
return 0;
}
fc1735 发表于 2018-7-31 23:00
brute force
弱弱问下，有生之年这个程序能运行完吗？ 本帖最后由 fc1735 于 2019-10-5 13:39 编辑
gunjang 发表于 2019-8-11 21:30
弱弱问下，有生之年这个程序能运行完吗？
S = map(lambda x: x**2, range(1, 101))
U = list(map(lambda x: {}, range(51)))
U = 1
for i in S:
for j in reversed(range(50)):
for k in U:
U = U.get(k+i, 0) + U
print(sum(map(lambda x: x, filter(lambda x: x == 1, U.items()))))
用python写的, 大约要跑2分钟, 不用dict的话可以1秒跑完
页:
[1]