7.2 動態規劃救背包問題#

def knapsack_dp(weights, values, W):
    """標準 O(nW) 一維 DP"""
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for j in range(W, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[W]

def subset_sum_bitset(nums, t):
    """位元平行的子集和：O(n * t / 64)"""
    bits = 1                       # 第 0 位 = 1（和 0 可達）
    mask = (1 << (t + 1)) - 1      # 只保留 t 位以內
    for s in nums:
        bits = (bits | (bits << s)) & mask
    return (bits >> t) & 1 == 1

def knapsack_by_value(weights, values, W):
    """以價值為狀態：O(n * ΣV)，回傳最大價值"""
    total_v = sum(values)
    INF = float('inf')
    minw = [INF] * (total_v + 1)
    minw[0] = 0
    for w, v in zip(weights, values):
        for u in range(total_v, v - 1, -1):
            if minw[u - v] + w <= W and \
               minw[u - v] + w < minw[u]:
                minw[u] = minw[u - v] + w
    return max(v for v in range(total_v + 1)
               if minw[v] <= W)

import random, time
weights = [random.randint(1, 1000) for _ in range(200)]
values  = [random.randint(1, 1000) for _ in range(200)]
W = 50000
t0 = time.time()
print("容量版 DP:", knapsack_dp(weights, values, W),
      f"{time.time()-t0:.3f}s")
t0 = time.time()
print("價值版 DP:", knapsack_by_value(weights, values, W),
      f"{time.time()-t0:.3f}s")
print("位元平行子集和可達 12345:",
      subset_sum_bitset(weights, 12345))