OJ Board

Posted: **Mon Apr 03, 2006 5:46 pm**

There is a set of N integers in range [-1000, 1000], N< 1000
I have to find if there is any subset which sum of elements is exactly S.
S is an integer in range [-1 000 000, 1 000 000 ]

Example:

Set - {5, 10, 25, 50}
S = 30
I can find a subset {5,25} - 5+25 = 30

Set - { -6,9,100,-45}
S = -42
I can find a subset {-6,9,-45} - (-6)+9+(-45) = 3 + (-45) = (-42)

Set - {-5, 10, 20, 100}
Set = 3
I can't find any set which sum is exacly 3.

Please help

Posted: **Tue Apr 04, 2006 10:07 pm**

http://www.comp.nus.edu.sg/~stevenha/pr ... ing_Change

Posted: **Wed Apr 05, 2006 2:36 am**

Artikali wrote:http://www.comp.nus.edu.sg/~stevenha/pr ... ing_Change

Yours advice bad cose S very big {TLE I think}

Posted: **Wed Apr 05, 2006 12:34 pm**

This problem is NP-complete, so there's not much you can do if you want an exact solution and think that the straightforward (but exponential-time) dynamic programming solution will take too long.
Anyway I think the constraints are not high enough to preclude using the dp solution (of course this depends on the time limit, but I don't think anyone knows a better approach).

Posted: **Wed Apr 05, 2006 2:22 pm**

You can speed up the normal dp by a factor of about 8 if you use bits to store if a sum is reachable.

Posted: **Wed Apr 05, 2006 3:54 pm**

Thanks for your answers.
I've finally solve this problem.
I've created two arrays:
bool wasadd[2 000 001]
and
int sums[2 000 001]

It's "only"

2 000 000 possible sums.

I show my algorithm using example:
Set: 2,3,4 Sum to find: 7

wassadd[2+1 000 000] = 1;
sums[0] = 2;

Code: Select all

for members of set from 3 to 4 do
	for every integer in sums array:
	if (wassad[sums[x]+actual member of set+ 1 000 000]==0) 
		add sums[x]+actual member to sums array
		wassad[sums[x]+actual member of set+ 1 000 000]=1

if (wassad[sumtofind + 1 000 000]==1) i can find sum in this set

State of arrays sums and wasadd for each step of algoritm

Fristly
wassad: 1 000 002 are "1"
sums: 2

Actual member of set - 3
wassad: 1 000 002, 1 000 003, 1 000 005 are "1"
sums: 2, 3, 5

Aktual member of set - 4
wassad: 1 000 002, 1 000 003, 1 000 005, 1 000 004, 1 000 006, 1 000 007, , 1 000 009 are "1"
sums: 2, 3, 5, 4, 6, 7, 9

1 000 007 is "1" so I can find subset which sum is 7

I hope you understand

OJ Board

Problem with sum of seqence

Problem with sum of seqence