Bài toán cái túi (knapsack problem) là một bài toán tối ưu hóa, trong đó chúng ta cần tìm cách chọn một tập hợp các món đồ có giá trị cao nhất mà vẫn có thể đựng được vào một cái túi với dung tích giới hạn. Đây là một bài toán cực kỳ phổ biến trong lĩnh vực tối ưu hóa và tính toán.
Thuật toán quy hoạch động (Dynamic Programming)
def knapsack_dp(values, weights, max_weight):
n = len(values)
dp = [[0 for j in range(max_weight+1)] for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, max_weight+1):
if weights[i-1] > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
return dp[n][max_weight]
Thuật toán tham lam (Greedy Algorithm)
def knapsack_greedy(values, weights, max_weight):
n = len(values)
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
total_value = 0
for v, w in items:
if max_weight >= w:
max_weight -= w
total_value += v
else:
total_value += max_weight * (v/w)
break
return total_value
Thuật toán quy hoạch định hướng (Branch and Bound)
import heapq
class Node:
def __init__(self, level, value, weight, bound, includes):
self.level = level
self.value = value
self.weight = weight
self.bound = bound
self.includes = includes
def __lt__(self, other):
return self.bound > other.bound
def knapsack_branch_bound(values, weights, max_weight):
n = len(values)
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
queue = []
best_value = 0
root = Node(-1, 0, 0, 0, [])
root.bound = bound(root, items, n, max_weight)
heapq.heappush(queue, root)
while queue:
node = heapq.heappop(queue)
if node.bound > best_value:
if node.level == n-1:
best_value = node.value
else:
next_level = node.level + 1
next_include = node.includes + [next_level]
next_weight = node.weight + items[next_level][1]
if next_weight <= max_weight:
next_value = node.value + items[next_level][0]
next_node = Node(next_level, next_value, next_weight, 0, next_include)
next_node.bound = bound(next_node, items, n, max_weight)
if next_node.bound > best_value:
heapq.heappush(queue, next_node)
include = node.includes
exclude = include[:-1] + [node.level+1]
if bound(node, items, n, max_weight) > best_value:
exclude_node = Node(node.level+1, node.value, node.weight, 0, exclude)
exclude_node.bound = bound(exclude_node, items, n, max_weight)
if exclude_node.bound > best_value:
heapq.heappush(queue, exclude_node)
return best_value
def bound(node, items, n, max_weight):
if node.weight >= max_weight:
return 0
value = node.value
weight = node.weight
level = node.level + 1
while level < n and weight + items[level][1] <= max_weight:
weight += items[level][1]
value += items[level][0]
level += 1
if level < n:
value += (max_weight - weight) * items[level][0] / items[level][1]
return value
Trên đây là ba cách giải bài toán cái túi trong Python, bao gồm thuật toán Quy hoạch động, thuật toán Tham lam và thuật toán Quy hoạch định hướng. Mỗi thuật toán có ưu điểm và nhược điểm khác nhau và thường được sử dụng tùy thuộc vào đặc điểm của từng bài toán cụ thể.
Cài đặt một ví dụ với thuật toán quy hoạch động
Dưới đây là một ví dụ minh họa cho bài toán cái túi được giải bằng thuật toán quy hoạch động trong Python.
Giả sử chúng ta có một cái túi có dung tích tối đa là 50 đơn vị và có các món đồ sau đây:
values = [60, 100, 120]
weights = [10, 20, 30]
Chúng ta cần chọn các món đồ có giá trị cao nhất mà vẫn có thể đựng được vào cái túi.
Sử dụng thuật toán quy hoạch động, ta có thể giải bài toán như sau:
def knapsack_dp(values, weights, max_weight):
n = len(values)
dp = [[0 for j in range(max_weight+1)] for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, max_weight+1):
if weights[i-1] > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
return dp[n][max_weight]
values = [60, 100, 120]
weights = [10, 20, 30]
max_weight = 50
max_value = knapsack_dp(values, weights, max_weight)
print("Các món đồ được chọn:")
for i in range(len(values), 0, -1):
if max_value == 0:
break
if max_value == dp[i-1][max_weight]:
continue
else:
print(f"Item {i} (value={values[i-1]}, weight={weights[i-1]})")
max_value -= values[i-1]
max_weight -= weights[i-1]
print("Tổng giá trị của các món đồ được chọn là:", knapsack_dp(values, weights, max_weight))
Kết quả đầu ra sẽ là:
Các món đồ được chọn:
Item 3 (value=120, weight=30)
Item 2 (value=100, weight=20)
Tổng giá trị của các món đồ được chọn là: 220
Ở ví dụ này, thuật toán quy hoạch động đã chọn hai món đồ cuối cùng vì chúng có giá trị cao hơn món đồ đầu tiên và có thể đựng được vào cái túi. Tổng giá trị của các món đồ được chọn là 220.