Knapsack Problem
When we meet the problem which requires to use the multiple resources to get the max benefits under some limitation, when may use the Knapsack Problem approach to solve the problem.
0-1 Knapsack Problem
Link: http://love-oriented.com/pack/P01.html
Using multiple items, each item has a size and a value to fill a bag with the fixed size. And each item only can be used once. What's the max benefits we can get by filling this bag by items.
- What's the max benefits, when we must fully fill this bag.
- What's the max benefits, when we don't need fully fill this bag.
Formula:
if size >= items[i].size
benefits[i][size] = max(
benefits[i - 1][size],
benefits[i - 1][size - items[i].size] + items[i].value
)
Explanation for formula:
The 'benefits[i][size]' means the max benefits we can get by fully filling the bag whose size is 'size' with the set of items (items[0], items[1], items[2]...items[i]).
Each time, we just need focus on whether we put the current item (items[i]) into the bag or not. If we don't put the current item into the bag, the max benefits for fully filling the bag whose size is 'size' is equal to the max benefits we can get by fully filling the bag whose size is 'size' with the items (items[0], items[1], items[2]...items[i - 1]). If we put the current item into the bag, the max benefits for fully filling the bag whose size is 'size' is equal to the max benefits we can get by fully filling the bag whose size is 'size - items[i].size' with the items (items[0], items[1], items[2]...items[i - 1]) plus the value of the current item (items[i].value).
Note:
- If we must fully fill the bag, we should initialize the benefits[i][0] = 0, benefits[i][others] = min_int.
- If we don't need fully full the bag, we should initialize the benefits[i][all] = 0.
Explanation:
The initial benefits matrix should contain the valid value, when we haven't put any item into the bag.
- If we must fully fill the bag, at this moment, we only know we can put one item whose value is 0 to the bag whose size is 0 to make it get the max benefit, so we can set benefits[i][0] = 0. But for other bags whose sizes are not 0, we don't know what's the valid max benefits that those bags can get, so we set "minimum int" to those bag's benefits, which means at this moment we still don't know the valid value, so we use a meaningless value (min int) here.
- If we don't need to fully fill he bag, we know the 0 is a valid value to all bags' benefits, so we can set benefits[i][all] = 0.
import sys
class Item(object):
def __init__(self, size, value):
self.size = size
self.value = value
def validate(bag_size, items):
if bag_size < 0 or items is None:
return False
return True
def get_max_benefits_when_fill_bag_fully(bag_size, items):
# time complexity = O(bag_size * len(items))
# space complexity = O(bag_size * len(items))
if not validate(bag_size, items):
raise ValueError('bag_size or items are not vaild')
# init benefits
benefits = [[-sys.maxint - 1 for col in xrange(bag_size + 1)] for row in xrange(len(items) + 1)]
for i in xrange(len(items) + 1):
benefits[i][0] = 0
for i in xrange(1, len(items) + 1):
item = items[i - 1]
for size in xrange(bag_size + 1):
if size >= item.size:
benefits[i][size] = max(benefits[i - 1][size],
benefits[i - 1][size - item.size] + item.value)
else:
benefits[i][size] = benefits[i - 1][size]
return benefits[len(items)][bag_size]
def get_max_benefits_when_fill_bag_fully_space_optimization(bag_size, items):
# time complexity = O(bag_size * len(items))
# space complexity = O(bag_size)
if not validate(bag_size, items):
raise ValueError('bag_size or items are not valid')
# init benefits
benefits = [-sys.maxint - 1 for x in xrange(bag_size + 1)]
benefits[0] = 0
for item in items:
# note:
# when the bag size is 0, the benefits[0] is always 0,
# so here we only need iterate size from bag_size to 1.
for size in xrange(bag_size, 0, -1):
if size >= item.size:
benefits[size] = max(benefits[size],
benefits[size - item.size] + item.value)
return benefits[bag_size]
def get_max_benefits_no_need_fill_bag_fully(bag_size, items):
# time complexity = O(bag_size * len(items))
# space complexity = O(bag_size * len(items))
if not validate(bag_size, items):
raise ValueError('bag_size or items are not valid')
# init benefits
benefits = [[0 for col in xrange(bag_size + 1)] for row in xrange(len(items) + 1)]
for i in xrange(1, len(items) + 1):
item = items[i - 1]
for size in xrange(bag_size + 1):
if size >= item.size:
benefits[i][size] = max(benefits[i - 1][size],
benefits[i - 1][size - item.size] + item.value)
else:
benefits[i][size] = benefits[i - 1][size]
return benefits[len(items)][bag_size]
def get_max_benefits_no_need_fill_bag_fully_space_optimization(bag_size, items):
# time complexity = O(bag_size * len(items))
# space complexity = O(bag_size)
if not validate(bag_size, items):
raise ValueError('bag_size or items are not valid')
# init benefits
benefits = [0 for x in xrange(bag_size + 1)]
for item in items:
for size in xrange(bag_size, 0, -1):
if size >= item.size:
benefits[size] = max(benefits[size],
benefits[size - item.size] + item.value)
return benefits[bag_size]
if __name__ == '__main__':
bag_size = 15
items = [Item(12, 4), Item(2, 2), Item(1, 2), Item(1, 1), Item(4, 10)]
print get_max_benefits_when_fill_bag_fully(bag_size, items)
print get_max_benefits_when_fill_bag_fully_space_optimization(bag_size, items)
print get_max_benefits_no_need_fill_bag_fully(bag_size, items)
print get_max_benefits_no_need_fill_bag_fully_space_optimization(bag_size, items)
Note:
- In the non-space optimization solution, we use 'if-else' inside the most inner loop, because when the current item cannot fit current size, we will not put the current item into the bag. So the max benefits[i][size] is equivalent to the max benefits[i - 1][size].
- We use 'len(items) + 1' to initialize the benefits matrix's first dimension, because we want to avoid the 'i - 1' to be '-1'.
Note:
When we use the two dimensional matrix in the iteration to solve the problem, we can think about that we may traverse the matrix row by row, and column by column (from right to left) to save one dimension space.
For example:
The bag_size = 15
The items are: [{size=12, value=4}, {size=2, size=2}, {size=1, value=2}, {size=1, value=1}, {size=4, value=10}]
- If we must fill the bag fully, the best solution is {size=12, value=4} + {size=2, value=2} + {size=1, value=2}, and the max benefit is 8(value).
- If we no need fill the bag fully, the best solution is {size=2, value=2} + {size=1, value=2} + {size=1, value=1} + {size=4, value=10}, and the max benefit is 15.
Complete Knapsack Problem
Link: http://love-oriented.com/pack/P02.html
Using multiple items, each item has(size, value) to fill the bag with the fixed size, and each item can be used unlimited times. What's the max benefits we can get by filling this bag with these items.
- What's the max benefits we can get, when we must fully fill this bag.
- What's the max benefits we can get, when we don't need fully fill this bag.
Formula:
if size >= items[i].size
benefits[i][size] = max(
benefits[i - 1][size],
benefits[i - 1][size - k * items[i].size] + k * items[i].value
)
0 <= k * items[i].size <= size
Note:
- If we must fully fill this bag, we should initialize benefits[i][0] = 0, and benefits[i][others] = min_int.
- If we don't need fully fill this bag, we should initialize benefits[i][all] = 0.
import sys
class Item(object):
def __init__(self, size, value):
self.size = size
self.value = value
def validate(bag_size, items):
if bag_size < 0 or items is None:
return False
return True
def get_max_benefits_when_fully_fill_bag(bag_size, items):
# time complexity = O(len(items) * bag_size * (bag_size / items[i].size))
# space complexity = O(len(items) * bag_size)
if not validate(bag_size, items):
raise ValueError('bag_size or items are not valid')
# init benefits
benefits = [[-sys.maxint - 1 for j in xrange(bag_size + 1)] for i in xrange(len(items) + 1)]
for i in xrange(len(items) + 1):
benefits[i][0] = 0
for i in xrange(1, len(items) + 1):
item = items[i - 1]
for size in xrange(bag_size + 1):
benefits[i][size] = benefits[i - 1][size]
k = 0
while k * item.size <= size:
benefits[i][size] = max(benefits[i - 1][size],
benefits[i - 1][size - k * item.size] + k * item.value)
k += 1
return benefits[len(items)][bag_size]
def get_max_benefits_when_fully_fill_bag_space_optimization(bag_size, items):
# time complexity = O(len(items) * bag_size)
# space complexity = O(bag_size)
if not validate(bag_size, items):
raise ValueError('bag_size or items are not valid')
# init benefits
benefits = [-sys.maxint - 1 for x in xrange(bag_size + 1)]
benefits[0] = 0
for item in items:
for size in xrange(1, bag_size + 1):
if size >= item.size:
benefits[size] = max(benefits[size], benefits[size - item.size] + item.value)
return benefits[bag_size]
def get_max_benefits_when_no_need_fully_fill_bag(bag_size, items):
# time complexity = O(len(items) * bag_size * (bag_size / items[i].size))
# space complexity = O(len(items) * bag_size)
if not validate(bag_size, items):
raise ValueError('bag_size or items are not valid')
# init benefits
benefits = [[0 for j in xrange(bag_size + 1)] for i in xrange(len(items) + 1)]
for i in xrange(1, len(items) + 1):
item = items[i - 1]
for size in xrange(bag_size + 1):
benefits[i][size] = benefits[i - 1][size]
k = 0
while k * item.size <= size:
benefits[i][size] = max(benefits[i - 1][size],
benefits[i - 1][size - k * item.size] + k * item.value)
k += 1
return benefits[len(items)][bag_size]
def get_max_benefits_when_no_need_fully_fill_bag_space_optimization(bag_size, items):
# time complexity = O(len(items) * bag_size)
# space complexity = O(bag_size)
if not validate(bag_size, items):
raise ValueError('bag_size or items are not valid')
# init benefits
benefits = [0 for x in xrange(bag_size + 1)]
for item in items:
for size in xrange(bag_size + 1):
if size >= item.size:
benefits[size] = max(benefits[size], benefits[size - item.size] + item.value)
return benefits[bag_size]
if __name__ == '__main__':
bag_size = 15
items = [Item(12, 4), Item(2, 2), Item(1, 2), Item(1, 1), Item(4, 10)]
print get_max_benefits_when_fully_fill_bag(bag_size, items)
print get_max_benefits_when_fully_fill_bag_space_optimization(bag_size, items)
print get_max_benefits_when_no_need_fully_fill_bag(bag_size, items)
print get_max_benefits_when_no_need_fully_fill_bag_space_optimization(bag_size, items)
How to understand the space optimization solution: