CODEWITHSUNDEEP
arraysalgorithm
Amol Sharma
Amol Sharma

Reputation: 1591

Maximum Sum less than a Limit

I have been trying to solve the Problem http://www.spoj.pl/problems/RPLB/ but not able to come up with a algo.

my attempts -

  1. Divide the input in two arrays, one is values at odd indexes and other with values at even indexes. After that, sort both the arrays and adding the numbers till the sum is less than the limit. I was soon able to got the flaw with some test cases.

  2. I stored the input in a array and and each time i tried to add largest remaining number on condition that it is not adjacent to any number already added but this algo too turned out to be wrong.

Now, only solution i am able to think is exponential by trying all possible combinations :(

Please suggest what's the correct algo to solve this problem.

Upvotes: 0

Views: 603

Answers (2)

Antti Huima
Antti Huima

Reputation: 25512

This is the KNAPSACK problem with an additional constraint (that you can't pick two adjacent bushes), and the additional constraint does not make it easier nor harder. As it is as hard as KNAPSACK, i.e. NP-complete, there isn't essentially much else to do except brute force search (which can be optimized but will remain exponential / super-polynomial anyway).

Upvotes: 1

Thomash
Thomash

Reputation: 6379

This is a well-known NP hard problem, so don't worry if your solution is exponential.

Upvotes: 0

Related Questions