Multiple knapsack problem python

Solving the Multiple Knapsack Problem with Google OR tools

A step-by-step walkthrough of using linear programming in Python to solve the Multi-Constrained Multi-Knapsack Problem.

Introduction

The knapsack problem is a toy problem used in linear programming for a user to learn how to formulate an equation that will optimally pack a knapsack with items of various weights. Each item usually has an associated value as well. The goal is to optimize the value of the backpack while not exceeding the weight limit of the bag. Today’s problem extends from the basic knapsack problem to a multiple knapsack problem with multiple constraints. The code and walkthrough provide are similar to what can be found on Goole OR Tools, however, the problem being solved today has more constraints.

Problem

You and 4 scientists are researching the radioactive properties of different combinations of elements to find a new clean energy source for the planet. While the radioactive levels in the elements and mixtures are low, you decided that you want to hike out to a remote lab to ensure the safety of the civilian population. Each of you has 1 element packing bag that has the ability to hold 50 pounds (lbs) of weight and a volume capacity of 50 cubic inches. In addition, you and the group can only be exposed to maximum radioactivity of 25 rads, therefore, each bag can only have a maximum of 5 rads to ensure safety that no one’s bag has too much radiation and is hurting the carrier. Each element has a certain level of value (utils) and the goal of the team is to pick the best combination of items that maximize your team’s utility while still safely packing the 5 bags. How should the 5 bags be packed with the given item? (The words “Bag” and “Knapsack” are interchangeable)

Setting up the Problem

First, import OR tools (Probably will have to conduct a pip install!)

import ortools
from ortools.linear_solver import pywraplp

We are solving a linear program and therefore need to import pywraplp from ortools.linear_solver. Next, create the solver.

solver = solver = pywraplp.Solver.CreateSolver('SCIP')

Источник

USM-F / MCKP.py

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

#groups is list of integers in ascending order without gaps

def getRow ( lists , row ):

res = []

for l in lists :

for i in range ( len ( l )):

if i == row :

res . append ( l [ i ])

return res

def multipleChoiceKnapsack ( W , weights , values , groups ):

n = len ( values )

K = [[ 0 for x in range ( W + 1 )] for x in range ( n + 1 )]

for w in range ( W + 1 ):

for i in range ( n + 1 ):

if i == 0 or w == 0 :

K [ i ][ w ] = 0

elif weights [ i — 1 ]

sub_max = 0

prev_group = groups [ i — 1 ] — 1

sub_K = getRow ( K , w — weights [ i — 1 ])

for j in range ( n + 1 ):

if groups [ j — 1 ] == prev_group and sub_K [ j ] > sub_max :

sub_max = sub_K [ j ]

K [ i ][ w ] = max ( sub_max + values [ i — 1 ], K [ i — 1 ][ w ])

else :

K [ i ][ w ] = K [ i — 1 ][ w ]

return K [ n ][ W ]

#Example

values = [ 60 , 100 , 120 ]

weights = [ 10 , 20 , 30 ]

groups = [ 0 , 1 , 2 ]

W = 50

print ( multipleChoiceKnapsack ( W , weights , values , groups )) #220

Источник

Multiple knapsacks by Binary Optimization | Python Theme month

In the last lecture, we said that the multiple knapsack problem cannot be reduced by one-dimensional optimization in the same way as the full knapsack problem.

At the same time, items in multiple backpacks are «flattened», which can be completely transformed into the 01 backpack problem.

However, as the number of items is not reduced, the enumeration will not be reduced, and the time complexity will not change, but increase the cost of flattening, making the constant of the algorithm larger.

In the case of the same order of magnitude in each dimension, the time complexity of the multiple knapsack we have learned can only solve problems of order of magnitude.

Topic describes

There are items and a backpack with a capacity of 5, and each item is «limited in quantity».

The volume of the first item is, the value is, and the quantity is.

Ask which items to choose and how many items to choose for each item to maximize the total value.

In fact, based on the 0-1 knapsack problem, it added the feature that each item can be selected «a limited number of times» (as capacity allows).

Input: N = 2, C = 5, V = [1,2], W = [1,2], s = [2,1] Output: 4Copy the code

Binary optimization

Binary optimization can increase the number of multiple knapsack problems we can solve from an order of magnitude to.

Binary optimization refers to how we can completely transform a multiple knapsack problem into a 0-1 knapsack problem while reducing its complexity.

In the last section we flattened directly, an item of quantity is equivalent to.

This doesn’t reduce the amount of computation, but if we can get to less than, then this flattening makes sense.

If you have learned Linux, you know that the highest file permissions are 7, which means that you have read, write, and execute permissions. However, in fact, this 7 corresponds to 1, 2, and 4, namely r:1, W :2, and X :4. There are altogether 8 possible combinations of these three permissions.

Here we use the «compression» method of three numbers corresponding to eight cases.

We can also learn from this idea: replace n items with ceiL (log(n)) numbers to reduce algorithm complexity.

7 can be replaced with 1, 2, 4, like 10, we can replace it with 1, 2, 4, 3, and you might wonder, why 1, 2, 4, 3, instead of 1, 2, 4, 6 or 1, 2, 4, 8?

1, 2, 4, 6 can express the range of 0 13, while 1, 2, 4, 8 can express the range of 0 15, and we want to express the range of 10, greater than 10 can not be selected.

So we can add a number 3 (from 10-7) on the basis of 1, 2 and 4 (the range of expression is 0 and 7), which can satisfy the range of expression 0 and 10.

Take a look at the code that solves the multiple knapsack problem by flattening.

class Solution < public int maxValue(int N, int C, int[] s, int[] v, int[] w) < / / flat ListInteger worth = new ArrayList(); ListInteger volume = new ArrayList(); // We want everything to be flat, so we walk through everything first for (int i = 0; i N; i++) < // Get the number of occurrences per item int val = s[i]; // Flatten: If an item is used 7 times, we flatten it into 3 items: 1* weight 1* value, 2* weight 2* value, and 4* weight 4* value // Selecting the first flat item corresponds to using the item once. Selecting the second flat item corresponds to using the item twice. Selecting the first and second flat item corresponds to using the item 3 times. for (int k = 1; k = val; k *= 2) < val -= k; worth.add(w[i] * k); volume.add(v[i] * k); >if (val 0) < worth.add(w[i] * val); volume.add(v[i] * val); >>// 0-1 Knapsack problem solution int[] dp = new int[C + 1]; for (int i = 0; i worth.size(); i++) < for (intj = C; j = volume.get(i); j--) < dp[j] = Math.max(dp[j], dp[j - volume.get(i)] + worth.get(i)); >>returndp[C]; >>Copy the code

class Solution: def maxValue(self, N, C, s, v, w) : # flat worth = [] volume = [] # We wanted everything to be flat, so we walked through everything first for i in range(N): Get the number of occurrences per item val = s[i] # Flatten: If an item is required to be used 7 times, we flatten it into three items: 1* weight 1* value, 2* weight 2* Value, and 4* weight 4* Value # Selecting all three items corresponds to using the item 0 times, selecting only the first flat item corresponds to using the item 1 times, selecting only the second flat item corresponds to using the item 2 times, selecting only the first and second flat item corresponds to using the item 3 times. k = 1 while k = val: val -= k worth.append(w[i] * k) volume.append(v[i] * k) k *= 2 if val 0: worth.append(w[i] * val) volume.append(v[i] * val) # 0-1 Knapsack problem solution dp = [0] * (C + 1) for i in range(len(worth)): for j in range(C, volume[i] - 1, -1): dp[j] = max(dp[j], dp[j-volume[i]] + worth[i]) return dp[C] Copy the code

conclusion

Today we learned about binary optimization of «multiple knapsack».

Unlike ordinary flattening, which «directly split the first item into pieces», binary optimization can «split the original number of items into pieces», making the number of items after we converted to 01 knapbag decreased by an order of magnitude.

The «binary optimized» multiple knapsack can solve data range from up to one second.

But this is not the upper limit of multi-knapsack problem optimization, and in the next lecture we will introduce better optimization than binary optimization.

The last

This is the No.* of our «Brush through LeetCode» series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour.

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.

Источник