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 with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7 votes
0 answers

Estimate lagrangian multiplier based on instance characteristics

Assume we have a simple resource allocation problem, where all players have the same cost, but a different utility $a_s$. The resources assigned to a certain player must be between $L$ and $M$. ...
Pete S's user avatar
  • 123
5 votes
0 answers

What is the generalization of the resource allocation problem I'm dealing with here?

I'm dealing with a problem as follows: I have a finite set of money $m$ to spend over $r$ different raffles, and I need to spend approximately to my budget, with the goal of maximizing my probability ...
winterwyvern's user avatar
1 vote
0 answers

Finding the divisors of the numbers 2 to 13 as a knapsack problem

I don't know how to write this as Latex formulas, but here are anyways two examples, the divisors of $9$ and $12$ as the solutions to knapsack problems. Beware that there is some ...
Mats Granvik's user avatar
0 votes
0 answers

Why does changing this one thing in the Primal Effective Capacity Heuristic improve the solutions it generates for the MDK problem?

For a long-done project presentation, I implemented the Primal Effective Capacity (PECH) Heuristic to look for initial greedy solutions for the Multidimensional Knapsack (MDK) problem in Python. I ...
Miss Mae's user avatar
  • 121
0 votes
0 answers

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