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.

4 questions
Filter by
Sorted by
Tagged with
69k views

### 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 ...
• 852
2k views

### 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 ...
• 27.4k
4k views

### Subset sum problem implementation

Here is a recursive implementation of the Subset sum problem: ...
• 1,174