2
$\begingroup$

I have researched and am familiar with a few optimization problems. However, I can't seem to find material on what I'm attempting to solve in python.

Suppose you have 8 items of varying weight.

1;128
2;0
3;130
4;186
5;0
6;0
7;12
8;12

Let's say I have an unlimited amount of 'knapsacks'. I can only use 2 different items to fill each knapsack which can only hold a value of 90. Each time I load the knapsacks, I would like to then come back and make another pass with the remaining values.

For example: On the first pass, I can fit item 1 into a knapsack, item 3 in a knapsack, and item 4 in a knapsack.

On the next pass, even though I took 90 away from item 4, item 4 still holds a value of over 90, and I can put item 4 in another knapsack.

Is there is a specific term for this particular problem or a common solution? I would greatly appreciate any direction.

$\endgroup$
  • $\begingroup$ Your "knapsacks" do not have a capacity, or upper limit, so this is not a knapsack problem. What is the goal of shuffling things around then? I do not understand the definition of success. $\endgroup$ – Emre Jul 6 '17 at 18:50
  • $\begingroup$ Good call, these knapsacks can only hold 90. No more or no less. The goal is to minimize the value of each item by repeatedly taking at least 90 away from it. Or paring it with another item in a knapsack to equal 90. $\endgroup$ – Jake W Jul 6 '17 at 18:57
  • 1
    $\begingroup$ One approach is to solve the problem with a genetic algorithm (en.m.wikipedia.org/wiki/Genetic_algorithm). For inspiration, here is a nice collection of different approaches to a similar problem: kaggle.com/c/santas-uncertain-bags/kernels $\endgroup$ – tuomastik Jul 6 '17 at 19:13
  • $\begingroup$ Is your objective to find the most efficient way to move every item? $\endgroup$ – Dan Carter Jul 6 '17 at 19:49
  • $\begingroup$ I will take a look at what @tuomastik shared. Thank you. $\endgroup$ – Jake W Jul 6 '17 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.