Mô phỏng thuật toán Cái túi 0/1

0/1 Knapsack · Nhóm: Quy hoạch động

Cái túi 0/1 (0/1 Knapsack), nhóm Quy hoạch động.

Mã Python

def knapsack(w, v, n, W):
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for c in range(W+1):
            dp[i][c] = dp[i-1][c]
            if c >= w[i-1]:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w[i-1]] + v[i-1])
    return dp[n][W]

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.