CODEWITHSUNDEEP
pythonalgorithmgenetic-algorithm
Mark
Mark

Reputation: 2135

Knapsack (what?) in Python

I'm sorry for the title; frankly speaking, I don't even know whether my question is related to the Knapsack problem. Was reading some stuff about genetic algorithms and found this "Knapsack Problem".

I need someone to kick me in the right direction:

I am developing a python web application for a factory. So in a factory, they have something called an order. An order contains one or many products. There's a concept of mismatch, which is actually a negative number used to indicate how much less (in terms of quantity) a particular product will appear in an order.

Think of a matrix with the columns being products and the rows being orders. Just assume that all orders(rows) contain all products(columns). Again, there are 8 orders Orders 1 to Orders 8 and 5 products, Product 1 to Product 5.

Supposing, now I have a mismatch of 6 for Product 1. I need to split the number six equally amongst all 8 of the orders, randomly. So obviously 2 orders won't have mismatch quantities. Then I have a mismatch of 9 for Product 2. I split the mismatch quantity over 8 Orders as evenly as possible, randomly. This goes on for each Product. Now here comes the kicker, while I am in the process of splitting the mismatches randomly across all Orders, I need to ensure that the total mismatches per order (meaning for that row) are kept at a minimal. This means the total mismatches across an order needs to be the lowest possible number.

    |-----|-----|-----|-----|-----|
    |  P1 |  P2 |  P3 |  P4 |  P5 |
    -------------------------------
O1  |  2  |  1  |  1  |  0  |  2  |  6
    -------------------------------
O2  |  1  |  2  |  1  |  1  |  1  |  6
    -------------------------------
O3  |  2  |  2  |  1  |  0  |  1  |  6
    -------------------------------
O4  |  1  |  2  |  0  |  1  |  1  |  5
    -------------------------------
       6     7     3     2     5

Do you get it? I need to code this in Python, and I have no idea where to start.

Upvotes: 3

Views: 1228

Answers (3)

xvatar
xvatar

Reputation: 3259

So the OP's problem has two requirements: randomly and evenly. It's a bit conflicting though, so I guess "truly random" is impossible.

Here is my try

Using OP's example, we have 4 orders and 5 products. Starting from the first product, we split the numbers randomly, so each product will at least have floor(6/4)=1 mismatches. Then we randomly put the remaining 2 mismatches to 2 products.

    |-----|
    |  P1 |
    -------
O1  |  2  | 2
    -------
O2  |  1  | 1
    -------
O3  |  2  | 2
    -------
O4  |  1  | 1
    -------
       6

Next, we take care of the second product. Similarly, we split the numbers randomly first, so each product will at least have floor(7/4)=1 mismatches. Now for the remaining 3 mismatches, to make it as even as possible, we first assign them to O2 and O4, since last time they have 1 less mismatch than others. For the remaining 1 mismatches, we again randomly assign it to one of the product.

    |-----|-----|
    |  P1 |  P2 |
    -------------
O1  |  2  |  1  | 3
    -------------
O2  |  1  |  2  | 3
    -------------
O3  |  2  |  2  | 4
    -------------
O4  |  1  |  2  | 3
    -------------
       6     7

Repeat this process for all the products.

Using this way, you can guarantee that it's as even as possible (the biggest difference is 1), also you get some degree of random

Upvotes: 1

MRAB
MRAB

Reputation: 20664

Suppose you do it this way:

You have a sequence of items to put into the orders, the sequence consisting of items of the first product, followed by items of the second product, etc.

You put the first item into the first order, the second item into the second order, etc, wrapping around at some point to the first order again, round and round, until you have no more items.

Would that work?

Upvotes: 0

chepner
chepner

Reputation: 532063

You almost have an integer linear programming problem, except that the objective function (the maximum of the row sums) you want to minimize is not linear. Look at scipy for solving optimization problems.

This thread, https://scicomp.stackexchange.com/questions/83/is-there-a-high-quality-nonlinear-programming-solver-for-python, may also help.

Upvotes: 2

Related Questions