The challenge is to produce an algorithm to solve the Subset-Sum Problem in your language of choice. To make it somewhat interesting try to make it as efficient as possible and do not copy an existing algorithm but come up with one yourself.
Bonus Points: Make the algorithm run in polynomial time.
>>20
Did you not read >>1 To make it somewhat interesting try to make it as efficient as possible and do not copy an existing algorithm but come up with one yourself.
I am almost done and will post my results soon (next 3 days)
>>25
the most beautiful thing about subset Sum problem is the inherent symmetry in everything. As you approach it with different methods and representations they all seamlessly blend into each other. It is almost like a million different ways to solve it in the same exact way.
Name:
Anonymous2008-05-11 17:16
>>27
That's funny. I feel the exact same way about 3-SAT.
Name:
Anonymous2008-05-11 17:57
>>28
Yes it will be glorious when /prog/ proves P=NP
Name:
Anonymous2008-05-11 20:20
O(n) complexity in Java: int max = list[0];
int maxStart, maxStop, start, sum;
for (int i = 0; i < list.length; i++) {
if (sum < 0) {
start = i;
sum = 0;
}
sum += list[i];
if (sum > max) {
max = sum;
maxStart = start;
maxStop = i;
}
}