Skip to main content

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.

Filter by
Sorted by
Tagged with
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 ...
Dave's user avatar
  • 233
8 votes
2 answers
768 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: ...
Cesar Canassa's user avatar
6 votes
1 answer
382 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 ...
Eddie's user avatar
  • 197
5 votes
1 answer
234 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{ ...
Max's user avatar
  • 564
0 votes
0 answers
227 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 ...
Matheus Diógenes Andrade's user avatar