Created
May 24, 2023 23:24
-
-
Save dimanyc/22924e3e08829ebcfb63c9997b487832 to your computer and use it in GitHub Desktop.
rucksack problem for materials
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
class Item: | |
def __init__(self, width, height, quantity): | |
self.width = width | |
self.height = height | |
self.quantity = quantity | |
class MaterialSheet: | |
def __init__(self, width, height): | |
self.width = width | |
self.height = height | |
def knapsack(items, material_sheets): | |
# Create a 2D matrix to store the maximum values | |
# achieved for each combination of items and capacity | |
dp = [[0] * (len(material_sheets) + 1) for _ in range(len(items) + 1)] | |
for i in range(1, len(items) + 1): | |
for j in range(1, len(material_sheets) + 1): | |
current_item = items[i - 1] | |
current_sheet = material_sheets[j - 1] | |
# Check if the current item can fit in the current sheet | |
if current_item.width <= current_sheet.width and current_item.height <= current_sheet.height: | |
# Calculate the remaining capacity | |
remaining_width = current_sheet.width - current_item.width | |
remaining_height = current_sheet.height - current_item.height | |
# Calculate the value of including the current item | |
include_value = current_item.quantity + dp[i - 1][j - 1] | |
# Calculate the value of excluding the current item | |
exclude_value = dp[i - 1][j] | |
# Choose the maximum value between including and excluding the current item | |
dp[i][j] = max(include_value, exclude_value) | |
else: | |
# If the current item cannot fit in the current sheet, exclude it | |
dp[i][j] = dp[i - 1][j] | |
return dp[-1][-1] | |
# Example usage | |
items = [ | |
Item(19.25, 82.5, 1), | |
Item(38, 82.5, 5), | |
Item(12.5, 82.5, 1), | |
Item(19.25, 61.5, 1) | |
] | |
material_sheets = [ | |
MaterialSheet(48, 96), | |
MaterialSheet(60, 96), | |
MaterialSheet(48, 120), | |
MaterialSheet(60, 120) | |
] | |
minimum_sheets = knapsack(items, material_sheets) | |
print(f"The minimum number of material sheets needed is: {minimum_sheets}") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment