ClassicComputerScienceProblemsInPython/Chapter9/knapsack.py at master · Ghost543/ClassicComputerScienceProblemsInPython · GitHub

History

63 lines (55 loc) · 2.52 KB

Raw

# knapsack.py

# From Classic Computer Science Problems in Python Chapter 9

# 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))

ClassicComputerScienceProblemsInPython/Chapter9/knapsack.py at master · Ghost543/ClassicComputerScienceProblemsInPython · GitHub

Expand file tree

Breadcrumbs

knapsack.py

Latest commit

History

Breadcrumbs

knapsack.py

File metadata and controls