Knapsack problem/Unbounded: Difference between revisions
Content deleted Content added
| Line 568: | Line 568: | ||
A dynamic programming approach using a 2-dimensional table (One dimension for weight and one for volume). Because this approach requires that all weights and volumes be integer, I multiplied the weights and volumes by enough to make them integer. This algorithm takes O(w*v) space and O(w*v*n) time, where w = weight of sack, v = volume of sack, n = number of types of items. To solve this specific problem it's much slower than the brute force solution. |
A dynamic programming approach using a 2-dimensional table (One dimension for weight and one for volume). Because this approach requires that all weights and volumes be integer, I multiplied the weights and volumes by enough to make them integer. This algorithm takes O(w*v) space and O(w*v*n) time, where w = weight of sack, v = volume of sack, n = number of types of items. To solve this specific problem it's much slower than the brute force solution. |
||
| ⚫ | |||
<python> |
|||
| ⚫ | |||
from collections import namedtuple |
from collections import namedtuple |
||
| Line 589: | Line 588: | ||
def tot_value(items_count): |
def tot_value(items_count, items, sack): |
||
""" |
""" |
||
Given the count of each item in the sack return -1 if they can't be carried or their total value. |
Given the count of each item in the sack return -1 if they can't be carried or their total value. |
||
| Line 596: | Line 595: | ||
values will minimise the weight if values tie, and minimise the volume if values and weights tie). |
values will minimise the weight if values tie, and minimise the volume if values and weights tie). |
||
""" |
""" |
||
global items, sack |
|||
weight = sum(n * item.weight for n, item in izip(items_count, items)) |
weight = sum(n * item.weight for n, item in izip(items_count, items)) |
||
volume = sum(n * item.volume for n, item in izip(items_count, items)) |
volume = sum(n * item.volume for n, item in izip(items_count, items)) |
||
| Line 605: | Line 603: | ||
def knapsack_dp(): |
def knapsack_dp(items, sack): |
||
""" |
""" |
||
Solves the Knapsack problem, with two sets of weights, |
Solves the Knapsack problem, with two sets of weights, |
||
using a dynamic programming approach |
using a dynamic programming approach |
||
""" |
""" |
||
global items, sack |
|||
# (weight+1) x (volume+1) table |
# (weight+1) x (volume+1) table |
||
# table[w][v] is the maximum value that can be achieved |
# table[w][v] is the maximum value that can be achieved |
||
| Line 637: | Line 633: | ||
while table[w][v]: |
while table[w][v]: |
||
# Find the last item that was added: |
# Find the last item that was added: |
||
aux = [table[w-item.weight][v-item.volume] + item.value for item in items] |
|||
i = aux.index(table[w][v]) |
|||
# Record it in the result, and remove it: |
# Record it in the result, and remove it: |
||
| Line 647: | Line 644: | ||
max_items = knapsack_dp() |
max_items = knapsack_dp(items, sack) |
||
max_value, max_weight, max_volume = |
max_value, max_weight, max_volume = tot_value(max_items, items, sack) |
||
max_weight = -max_weight |
max_weight = -max_weight |
||
max_volume = -max_volume |
max_volume = -max_volume |
||
| Line 655: | Line 652: | ||
item_names = ", ".join(item.name for item in items) |
item_names = ", ".join(item.name for item in items) |
||
print " The number of %s items to achieve this is: %s, respectively." % (item_names, max_items) |
print " The number of %s items to achieve this is: %s, respectively." % (item_names, max_items) |
||
print " The weight to carry is %.3g, and the volume used is %.3g." % (max_weight, max_volume) |
print " The weight to carry is %.3g, and the volume used is %.3g." % (max_weight, max_volume)</python> |
||
</python> |
|||
Sample output |
Sample output |
||