sum({1,3,6}) = 10,
sum({1,3,8}) = 12,
sum({1,3,10}) = 14,
sum({1,3,11}) = 15,
sum({1,6,8}) = 15,
sum({1,6,10}) = 17,
sum({1,6,11}) = 18,
sum({1,8,10}) = 19,
sum({1,8,11}) = 20,
sum({1,10,11}) = 22,
sum({3,6,8}) = 17,
sum({3,6,10}) = 19,
sum({3,6,11}) = 20,
sum({3,8,10}) = 21,
sum({3,8,11}) = 22,
sum({3,10,11}) = 24,
sum({6,8,10}) = 24,
sum({6,8,11}) = 25,
sum({6,10,11}) = 27,
sum({8,10,11}) = 29.
Görüldüğü üzere bazı toplamlar bir defa, bazıları çok defa gerçekleşmiştir.
Herhangi bir A kümesi için, k-elemanlı alt kümelerin bir defa gerçekleşen toplamları kümesi U(A,k) ile gösterilsin. Örneğe göre U(B,3) = {10,12,14,18,21,25,27,29} ve sum(U(B,3)) = 156 olur.
Şimdi, 100 elemanlı S = {12, 22, ... , 1002} kümesi ele alınsın. S kümesinin 50-elemanlı alt kümeleri sayısı 100891344545564193334812497256 dır.Buna göre sum(U(S,50)) kaçtır?
Cevap: 115039000.
Örnek algoritma: Java
public class p201 {
static int Elements[] = new int[100];
static final int SubsetSize = 50;
// static final int Elements[] = {1,3,6,8,10,11};
// static final int SubsetSize = 3;
static int MinN = 0;
static int MaxN = 0;
static byte Cache[][][]; // Max Index x Next Number x Next Sum Length
static int CountSums(int n,int sum_len,int max_idx)
{
if(n == 0) {
if(sum_len == 0) {
return 1;
} else {
return 0;
}
} else {
if(sum_len == 0) {
return 0;
} else {
if(max_idx >= 0) {
int S = 0;
for(int i = max_idx - 1;i >= 0 && S < 2;i--) {
int next_n = n - Elements[i];
int next_n_count;
if(next_n < 0) {
continue;
}
int next_sum_len = sum_len - 1;
if(Cache[i][next_n][next_sum_len] != -1) {
next_n_count = Cache[i][next_n][next_sum_len];
} else {
next_n_count = CountSums(next_n, next_sum_len, i);
Cache[i][next_n][next_sum_len] = (byte) next_n_count;
}
S += next_n_count;
}
return S;
} else {
return 0;
}
}
}
}
public static void main(String[] args)
{
long Solution = 0;
for(int i = 0;i < Elements.length;i++) {
Elements[i] = (i+1)*(i+1);
}
for(int i = 0;i < SubsetSize;i++) {
MinN += Elements[i];
}
for(int i = 0;i < SubsetSize;i++) {
MaxN += Elements[Elements.length - i - 1];
}
Cache = new byte[Elements.length + 1][MaxN + 1][SubsetSize + 1];
for(int i = 0;i < Elements.length;i++) {
for(int j = 0;j < MaxN;j++) {
for(int k = 0;k < SubsetSize;k++)
Cache[i][j][k] = -1;
}
}
for(int n = MinN;n <= MaxN;n++) {
int Sums = CountSums(n,SubsetSize,Elements.length);
if(Sums == 1) {
Solution += n;
}
}
System.out.println("Solution = " + Solution);
}
}Örnek algoritma: C/C++
#include<stdio.h>
#include<iostream>
#include<math.h>
const long long int MASK=(long long int)pow(2,50)-1;
const int LIMIT=340000;
long long int cs1[LIMIT]={0};
long long int cs2[LIMIT]={0};
int main(){
long long int ans=0;
for(int i=1;i<=100;i++){
int n=i*i;
for(int j=LIMIT-1-n;j-n>0;j--){
long long int p1=cs1[j];
long long int p2=(cs1[j-n]<<1)&MASK;
cs1[j]=(p1|p2);
long long int p3=(p1&p2);
cs2[j]=(cs2[j]|p3)|((cs2[j-n]<<1)&MASK);
}
cs1[n]=(cs1[n]|1);
}
for(int i=1;i<LIMIT;i++){
long long int p1=(cs1[i]>>49)&1;
long long int p2=(cs2[i]>>49)&1;
if(p1==1&&p2==0)ans+=i;
}
std::cout<<ans<<"\n";
}function y = euler201()
global memoGrid;
global Forbidden;
Forbidden = cell(100,100);
memoGrid = cell(100, 100);
S = (1:100).^2;
for i=1:50
for j=1:i
evalU(S,i,j);
end
end
for i=51:100
for j=50:-1:i-50
evalU(S,i,j);
end
end
y = sum(evalU(S,100,50));
function y = evalU(S, i, k)
global memoGrid;
global Forbidden;
if(~isequal(memoGrid{i,k},[]))
y = memoGrid{i,k};
return;
end
x = S(1:i);
if(k==1)
y = x;
elseif k==i
y = sum(x);
else
x1 = evalU(S,i-1,k-1)+S(i);
x2 = evalU(S,i-1,k);
xF = intersect(x1,x2);
Forbidden{i,k} = union(Forbidden{i-1,k},Forbidden{i-1,k-1}+S(i));
Forbidden{i,k} = union(Forbidden{i,k}, xF);
y = setdiff(setxor(x1,x2), Forbidden{i,k});
end
memoGrid{i,k} = y; #include<cstdio>
const int ms=300000;
int f[2][51][ms];
int main()
{
int s=0,t=1;
f[0][0][0]=f[1][0][0]=1;
for(int i=1,sum=1;i<=100;i++,sum+=i*i)
{
for(int j=1;j<=50&&j<=i;j++)
for(int k=1;k<ms&&k<=sum;k++)
{
f[t][j][k]=f[s][j][k];
if(k>=i*i)f[t][j][k]+=f[s][j-1][k-i*i];
}
s^=1,t^=1;
}
long long ans=0;
for(int i=0;i<ms;i++)
if(f[s][50][i]==1)ans+=i;
printf("%I64d\n",ans);
return 0;
} program pe201
! After generating some small test cases by using all combinations
! I saw pretty quick what I needed to do, but had a hard time figuring
! out how to store the necessary data so I could access it without searching.
! I considered various data structures (heap,red-black tree,etc.) but it became
! very complicated and confusing. Then I hit on the idea of using the sum and
! number of elements to reach the sum, as indices into an array with the value being
! the number of ways to reach the sum with that many elements. I could do it on
! paper for small cases, but I had a hard time finding a processing order that
! always worked. After much trial and error I ended up with the following:
!
implicit none
integer, parameter :: p_bsize = 100
integer, parameter :: p_subsize = 50
integer :: b(p_bsize)
integer, allocatable :: w(:,:)
integer :: bi,s,u,wu,ws,sm
integer :: maxsum
real (kind=8) :: time
call timeit(time)
do bi = 1,p_bsize
b(bi) = bi**2
end do
maxsum = sum(b(p_bsize - p_subsize + 1:p_bsize))
allocate (w(p_subsize,maxsum))
w = 0
do bi = 1,p_bsize
do s = maxsum,b(1),-1
do u = p_subsize-1,1,-1
if(w(u,s) > 0) then
wu = u + 1
ws = b(bi) + s
if(w(wu,ws) < p_subsize) then
w(wu,ws) = w(wu,ws) + w(u,s)
end if
end if
end do
end do
w(1,b(bi)) = 1
end do
sm = 0
do s = 1,maxsum
if(w(p_subsize,s) == 1) sm = sm + s
end do
write(6,*)' sum = ',sm
deallocate (w)
call elapsed(time)
stop
end