Mercurial > lbo > hg > juliaplay
view python/packing.py @ 40:5e3662b65004 default tip
Land/water find peak problem
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Mon, 03 Apr 2023 22:04:42 +0200 |
parents | 1ecfe01af17e |
children |
line wrap: on
line source
import numpy as np def knapsack(items=[4,3,1,2], profits=[60, 50, 20, 20], capacity=7): table = np.zeros((len(items)+1, capacity+1)) table[:, 0] = 0 table[0, :] = 0 for item in range(1, len(items)+1): for cap in range(1, capacity+1): y = 0 if items[item-1] > cap else profits[item-1]+table[item-1, cap-items[item-1]] table[item, cap] = max(table[item-1, cap], y) print(table) # Search path it, cap = len(items), capacity included = [False] * len(items) while it > 0: if table[it-1, cap-items[it-1]] == table[it, cap] - profits[it-1]: included[it-1] = True cap = cap - items[it-1] else: included[it-1] = False it -= 1 print(included) def binpacking(items=[1,5,5,2,4], profits=[4, 3, 2, 5, 1], capacity=5, bins=3): # Each bin is capacity+1 wide: one slot for "zero capacity" and then up to capacity. table = np.zeros((len(items)+1, bins*(capacity + 1))) table[:, 0] = 0 table[0, :] = 0 # Start with first bin: for item in range(1, len(items)+1): if items[item-1] > capacity: # Cannot pack this item; too large table[item, :] = table[item-1, :] continue for cap in range(1, bins * (capacity + 1)): # Current bin is cap//(capacity+1). if (cap - items[item-1]) // (capacity+1) == cap // (capacity+1) and (cap - items[item-1]) >= 0: # Fits current bin: we can pack table[item, cap] = max(table[item-1, cap], # no pack item profits[item-1] + table[item-1, cap - items[item-1]]) elif cap % capacity == 0: table[item, cap] = table[item, cap-1] else: table[item, cap] = max(table[item-1, cap], table[item, cap-1]) print(table) included = [False] * len(items) it, cap = len(items), (capacity+1) * bins - 1 while it > 0: if table[it-1, cap-items[it-1]] == table[it, cap] - profits[it-1]: included[it-1] = True cap = cap - items[it-1] else: included[it-1] = False it -= 1