■ 분할 가능 배낭 문제(Fractional Knapsack Problem)를 구현하는 방법을 보여준다.
▶ 예제 코드 (PY)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
from dataclasses import dataclass @dataclass class Item: name : str value : int weight : int def __init__(self, name, value, weight): self.name = name # 항목명 self.value = value # 항목의 가치 self.weight = weight # 항목의 무게 def solveKnapsackFractional(sourceItemList, capacity): sourceItemList.sort(key = lambda x : x.value / x.weight, reverse = True) maximumValue = 0 knapsackItemList = [] for sourceItem in sourceItemList: if sourceItem.weight <= capacity: knapsackItemList.append(sourceItem) capacity -= sourceItem.weight else: fraction = capacity / sourceItem.weight value = sourceItem.value * fraction if value > 0: knapsackItemList.append(Item(sourceItem.name, value, sourceItem.weight * fraction)) break for knapsackItem in knapsackItemList: maximumValue += knapsackItem.value return knapsackItemList, maximumValue sourceItemList = [ Item("물건 1", 120, 30), Item("물건 2", 200, 50), Item("물건 3", 150, 20), Item("물건 4", 80, 70), Item("물건 5", 100, 60) ] capacity = 100 knapsackItemList, totalValue = solveKnapsackFractional(sourceItemList, capacity) print(knapsackItemList) print(totalValue) """ [Item(name='물건 3', value=150, weight=20), Item(name='물건 1', value=120, weight=30), Item(name='물건 2', value=200, weight=50)] 470 """ |