Combinatorial optimization-typical problem-knapsack problem

Typical problem and execution method

Knapsack problem

A knapsack with a capacity of $ c (\ gt 0) $ and $ n $ luggage $ N = \ {1, \ dots, n \} $ are given. Let the capacity of the package $ i \ in N $ be $ w_i (\ gt 0) $ and the value be $ p_i (\ gt 0) $. Find an assortment of packages that maximizes the sum of values within the $ c $ capacity limit.

Execution method

usage


Signature: knapsack(size, weight, capacity)
Docstring:
Knapsack problem
Maximize value
input
    size:List of luggage sizes
    weight:List of luggage values
    capacity:capacity
output
Sum of values and list of selected packages

python


from ortoolpy import knapsack
size = [21, 11, 15, 9, 34, 25, 41, 52]
weight = [22, 12, 16, 10, 35, 26, 42, 53]
capacity = 100
print(knapsack(size, weight, capacity))

result


(105.0, [0, 1, 3, 4, 5])

python


# pandas.DataFrame
from ortoolpy.optimization import Knapsack
Knapsack('data/knapsack.csv', 100)
size weight
0 21 22
1 11 12
3 9 10
4 34 35
5 25 26

data

Recommended Posts

Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints
Combinatorial optimization-typical problems and execution methods