1
$\begingroup$

I have N amount of items, and each item has a weight and a value. I need to fit as many items as I can into a backpack, however they cannot exceed a weight of K. And I need to get the highest amount of value into the backpack without going over weight of K. And I can only use each item once.

This problem is an algorithmic problem, and while it is more related to computer science, I have a question about it that I thought would be best to ask here.

If I divide the value by the weight I get a ratio and call it X. I would then proceed to try and add the highest possible values to each other, without exceeding the weight limit. Would doing this allow me to find the highest possible value and the items that go in it everysingle time, or is this just a greedy solution that would only work part of the time?

$\endgroup$
  • $\begingroup$ This greedy algorithm does not guarantee the optimal solution. (If all weights are integers, this problem will become a very classic example of dynamic programming.) See en.wikipedia.org/wiki/Knapsack_problem for more information. $\endgroup$ – Tunococ Aug 2 '13 at 10:10
  • $\begingroup$ Yeah I thought it was too greedy and I would have to use DP. Thanks anyway though. $\endgroup$ – user2396852 Aug 2 '13 at 10:11
1
$\begingroup$

This greedy algorithm for the Knapsack problem is not optimal — however, it'll give you a $\frac12$-approximation of the best solution.

Using DP, you can get a pseudopolynomial time algorithm computing the optimal solution (it is not polynomial, as the running time depends on $K$, and not on $\log K$).

See Exercise 3.1, p.77 of Williamson and Shmoys, and more generally section 3.1 p. 65..

$\endgroup$
  • $\begingroup$ Okay thanks, yeah I thought I would have to do DP. Just started on my algorithm now, thanks. $\endgroup$ – user2396852 Aug 2 '13 at 10:33
  • $\begingroup$ @user2396852: observe that the DP algorithm will solve exactly the problem, but won't be polynomial-time. If you need a poly-time algorithm, the best you can hope for (unless a huge breakthrough in computational complexity is made) is a $(1+\epsilon)$-approximation algorithm. $\endgroup$ – Clement C. Aug 2 '13 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.