rucksack problem for materials

gistfile1.txt

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}")