forked from davecom/ClassicComputerScienceProblemsInPython
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathknapsack.py
More file actions
63 lines (55 loc) · 2.52 KB
/
Copy pathknapsack.py
File metadata and controls
63 lines (55 loc) · 2.52 KB
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
# knapsack.py
# From Classic Computer Science Problems in Python Chapter 9
# Copyright 2018 David Kopec
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
from typing import NamedTuple, List
class Item(NamedTuple):
name: str
weight: int
value: float
def knapsack(items: List[Item], max_capacity: int) -> List[Item]:
# build up dynamic programming table
table: List[List[float]] = [[0.0 for _ in range(max_capacity + 1)] for _ in range(len(items) + 1)]
for i, item in enumerate(items):
for capacity in range(1, max_capacity + 1):
previous_items_value: float = table[i][capacity]
if capacity >= item.weight: # item fits in knapsack
value_freeing_weight_for_item: float = table[i][capacity - item.weight]
# only take if more valuable than previous item
table[i + 1][capacity] = max(value_freeing_weight_for_item + item.value, previous_items_value)
else: # no room for this item
table[i + 1][capacity] = previous_items_value
# figure out solution from table
solution: List[Item] = []
capacity = max_capacity
for i in range(len(items), 0, -1): # work backwards
# was this item used?
if table[i - 1][capacity] != table[i][capacity]:
solution.append(items[i - 1])
# if the item was used, remove its weight
capacity -= items[i - 1].weight
return solution
if __name__ == "__main__":
items: List[Item] = [Item("television", 50, 500),
Item("candlesticks", 2, 300),
Item("stereo", 35, 400),
Item("laptop", 3, 1000),
Item("food", 15, 50),
Item("clothing", 20, 800),
Item("jewelry", 1, 4000),
Item("books", 100, 300),
Item("printer", 18, 30),
Item("refrigerator", 200, 700),
Item("painting", 10, 1000)]
print(knapsack(items, 75))