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.

Improve this question
$\endgroup$
6
  • $\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, 2017 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, 2017 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, 2017 at 19:13
  • $\begingroup$ Is your objective to find the most efficient way to move every item? $\endgroup$
    – Dan Carter
    Jul 6, 2017 at 19:49
  • $\begingroup$ I will take a look at what @tuomastik shared. Thank you. $\endgroup$
    – Jake W
    Jul 6, 2017 at 20:00

1 Answer 1

Reset to default
2
$\begingroup$

The problem is closer to bin packing - fix capacity container and the goal is find the minimum number of containers. You might want to looking into inverse bin packing problem - both the number of bins and their sizes are fixed, but the item sizes can be changed.

First-fit-decreasing bin packing algorithm might work.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.