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
5
votes
1answer
96 views

Solving a variant of multiple knapsack problem/ generalized assignment problem

Consider $m$ knapsack and $n$ items. With each knapsack $j$ associated a capacity $c(j)$ and with each item $i$ associated a profit $p(i,j)$ (that depends on the knapsack, so it's not exactly the ...
16
votes
3answers
3k views

Solving a knapsack problem with a lot of items

I am wondering what are the fastest ways(faster than classical dynamic programming) to solve the knapsack problem (to optimality) with $n$ items when $n$ is nearly equal to $10000$ ? Apart from ...
7
votes
1answer
99 views

How to convert 3D bin packing problem to 2D bin packing approximation?

I'm trying to approximately solve a 3D container loading problem. Is it possible to use 2D bin packing algorithms? If so, how do we make the transformation? What are the conditions needed to make the ...
12
votes
1answer
162 views

Looking for books in the same style as Hans Kellerer 2004, Knapsack Problems

I really enjoyed reading Hans Kellerer, David Pisinger, Ulrich Pferschy 2004 book Knapsack Problems. Can anybody recommend books in a similar style, about some other classes of problems / optimisation?...
7
votes
1answer
179 views

Shipments consolidation - how to model mutually exclusive items with OR-Tools CP Solver in Python (multi-knapsack, updated)

I am implementing a solution for packages consolidation (basing on Nurse Problem solution) with OR-Tools CP Solver. There is a factory that manufactures some small Packages that need to be ...
12
votes
3answers
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 ...
14
votes
1answer
673 views

Prove that these linear programming problems are bounded by $O(k^{1/2})$

Prove that these linear programming problems are bounded by $O(k^{1/2})$ The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this ...