Bài toán cái túi (0/1 Knapsack)

def knapsack(n, W, weights, values):
    """
    n: số đồ vật, W: sức chứa túi
    dp[i][w] = giá trị lớn nhất dùng i đồ vật đầu, túi sức chứa w
    """
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i-1][w]           # Không lấy đồ vật i
            if weights[i-1] <= w:
                lay = dp[i-1][w - weights[i-1]] + values[i-1]
                dp[i][w] = max(dp[i][w], lay)  # Lấy đồ vật i

    return dp[n][W]

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
W = 7
n = len(weights)
print(knapsack(n, W, weights, values))   # 9 (lấy đồ vật 2 và 3: 4+5 trọng 3+4=7)

def knapsack_1d(n, W, weights, values):
    """Phiên bản tối ưu bộ nhớ — O(W) không gian."""
    dp = [0] * (W + 1)

    for i in range(n):
        for w in range(W, weights[i] - 1, -1):  # Duyệt ngược!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
W = 7
print(knapsack_1d(len(weights), W, weights, values))   # 9

def knapsack_trace(n, W, weights, values):
    """Trả về (giá trị max, danh sách đồ vật đã chọn)."""
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i-1][w]
            if weights[i-1] <= w:
                lay = dp[i-1][w - weights[i-1]] + values[i-1]
                dp[i][w] = max(dp[i][w], lay)

    # Truy vết ngược
    da_chon = []
    w = W
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:   # Đồ vật i được lấy
            da_chon.append(i - 1)     # Chỉ số 0-based
            w -= weights[i-1]

    return dp[n][W], da_chon

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
max_val, chosen = knapsack_trace(4, 7, weights, values)
print(f"Giá trị max: {max_val}")           # 9
print(f"Đồ vật chọn (0-indexed): {chosen}")  # [2, 1] (đồ vật 3 và 2)

def co_the_chia_dau(arr):
    """
    Nếu tổng lẻ → không thể. Bằng không:
    kiểm tra có thể chọn tập con có tổng = tổng/2 không.
    → Knapsack với target = sum/2, value = weight.
    """
    tong = sum(arr)
    if tong % 2 != 0:
        return False
    target = tong // 2

    dp = [False] * (target + 1)
    dp[0] = True

    for x in arr:
        for w in range(target, x - 1, -1):
            dp[w] = dp[w] or dp[w - x]

    return dp[target]

print(co_the_chia_dau([1, 5, 11, 5]))   # True  (1+5+5 = 11)
print(co_the_chia_dau([1, 2, 3, 5]))    # False
print(co_the_chia_dau([1, 1, 1, 1]))    # True  (1+1 = 1+1)

def knapsack_khong_gioi_han(W, weights, values):
    """
    Duyệt w từ nhỏ đến lớn (xuôi): cho phép lấy lại đồ vật.
    Khác hoàn toàn 0/1 knapsack duyệt từ lớn đến nhỏ.
    """
    dp = [0] * (W + 1)
    for w in range(1, W + 1):
        for i in range(len(weights)):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# Ví dụ: đúc tượng vàng — có thể dùng nhiều thỏi cùng loại
weights = [1, 3, 4]
values  = [10, 40, 50]
print(knapsack_khong_gioi_han(7, weights, values))   # 80 (dùng 2 thỏi loại 2 + 1 thỏi loại 1: 40+40 trọng 6, còn 1 → 40+40+10=90? Hmm, 3+3+1=7, 40+40+10=90)
# Thực ra: 3+3+1=7, value=40+40+10=90

def so_cach_doi_tien(amount, coins):
    """
    dp[w] = số cách dùng các loại đồng xu để thành tổng w.
    Duyệt đồng xu ở ngoài, tổng ở trong → mỗi tổ hợp tính một lần.
    """
    dp = [0] * (amount + 1)
    dp[0] = 1   # 1 cách để tạo tổng 0 (không dùng đồng nào)

    for coin in coins:
        for w in range(coin, amount + 1):
            dp[w] += dp[w - coin]

    return dp[amount]

print(so_cach_doi_tien(5, [1, 2, 5]))    # 4  (5, 2+2+1, 2+1+1+1, 1*5)
print(so_cach_doi_tien(3, [2]))           # 0  (không thể)
print(so_cach_doi_tien(10, [10]))         # 1