Problem with sum of seqence

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
WRJ
New poster
Posts: 11
Joined: Sun Mar 19, 2006 8:28 pm

Problem with sum of seqence

Post by WRJ »

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 ;)

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post by Artikali »


QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

Post by QulinXao »

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

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david »

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).

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro »

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

WRJ
New poster
Posts: 11
Joined: Sun Mar 19, 2006 8:28 pm

Post by WRJ »

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 ;)

Post Reply

Return to “Algorithms”