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
57
votes
3
answers
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
6
votes
1
answer
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
3
votes
2
answers
4k
views
Subset sum problem implementation
Here is a recursive implementation of the Subset sum problem:
...
- 1,174
3
votes
1
answer
447
views
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 ...
- 389