Questions tagged [knapsack]
For questions related to the knapsack problem that seeks to find the number of each item to include in a limited container (in an integer knapsack or whether to include an item in a binary knapsack), given each item's weight and value, with the goal of maximizing the total value.
5
questions
13
votes
3
answers
1k
views
Allocating credit card points
I’m interested in the idea behind this in general, so I thought this would be the best place to post, though I have a practical and semi-urgent need of allocating the points on my credit card towards ...
- 233
8
votes
2
answers
691
views
knapsack problem with non-linear constraint
I have a basic knapsack problem where I need to fit the most weight possible in a bin:
...
- 215
6
votes
1
answer
371
views
Optimize for bonuses within a group (knapsack)
I am trying to create an LP problem which is like the knapsack problem but with groups of items. Let's say there are 10 groups of items each with up to 5 items. Each group has one special item and you ...
- 197
5
votes
1
answer
206
views
Dynamic program for knapsack in $O(W)$ space?
A familiar dynamic programming algorithm for the binary knapsack problem
$$
\begin{align}
\text{maximize}\quad & v \cdot x \\
\text{subject to} \quad & w \cdot x \leq W \\
\quad&x_i \text{ ...
- 524
0
votes
0
answers
197
views
Check VRP instance is feasibility
Beforehand, this is a very long thread, in case you want to know in advance, to see if this thread's interests match with yours, this thread concerns fast ways of determining whether a VRP instance is ...
- 1,198