CODEWITHSUNDEEP
algorithmlanguage-agnosticdynamic-programming
Albert
Albert

Reputation: 1123

Knapsack with unique elements

I'm trying to solve the following:

The knapsack problem is as follows: given a set of integers S={s1,s2,…,sn}, and a given target number T, find a subset of S that adds up exactly to T. For example, within S={1,2,5,9,10} there is a subset that adds up to T=22 but not T=23. Give a correct programming algorithm for knapsack that runs in O(nT) time.

but the only algorithm I could come up with is generating all the 1 to N combinations and try the sum out (exponential time).

I can't devise a dynamic programming solution since the fact that I can't reuse an object makes this problem different from a coin rest exchange problem and from a general knapsack problem.

Can somebody help me out with this or at least give me a hint?

Upvotes: 1

Views: 1327

Answers (2)

sonam khurana
sonam khurana

Reputation: 1

I did find a solution but with O(T(n2)) time complexity. If we make a table from bottom to top. In other words If we sort the array and start with the greatest number available and make a table where columns are the target values and rows the provided number. We will need to consider the sum of all possible ways of making i- cost [j] +j . Which will take n^2 time. And this multiplied with target.

Upvotes: 0

mrip
mrip

Reputation: 15163

The O(nT) running time gives you the hint: do dynamic programming on two axes. That is, let f(a,b) denote the maximum sum <= b which can be achieved with the first a integers.

f satisfies the recurrence

f(a,b) = max( f(a-1,b), f(a-1,b-s_a)+s_a )

since the first value is the maximum without using s_a and the second is the maximum including s_a. From here the DP algorithm should be straightforward, as should outputting the correct subset of S.

Upvotes: 2

Related Questions