As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [knapsack-problem]

The knapsack problem is a problem in combinatorial optimization: Given a set of items with associated weights and values, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and it maximizes the total value. It is an NP-complete problem, but several common simplifications are solved efficiently with dynamic programming.

Filter by
Sorted by
Tagged with
57 votes
3 answers

Dynamic programming knapsack solution

I wrote a solution to the Knapsack problem in Python, using a bottom-up dynamic programming algorithm. It correctly computes the optimal value, given a list of items with values and weights, and a ...
voithos's user avatar
  • 852
6 votes
1 answer

Python Knapsack problem: greedy

A tourist wants to make a good trip at the weekend with his friends. They will go to the mountains to see the wonders of nature, so he needs to pack well for the trip. He has a good knapsack for ...
Caridorc's user avatar
  • 27.4k
3 votes
2 answers

Subset sum problem implementation

Here is a recursive implementation of the Subset sum problem: ...
Ziezi's user avatar
  • 1,174
3 votes
1 answer

Code for dividing gifts equally

I recently came across this problem: It is Lavanya's birthday and several families have been invited for the birthday party. As is customary, all of them have brought gifts for Lavanya as well ...
hellozee's user avatar
  • 389