⚠️ 装不满的背包：贪心和最优

背包能装 10，三件物品是 (重量6,价值30)、(重量5,价值20)、(重量5,价值20)，每件要么整件拿走要么不拿。运行下面这段程序：

def knap_greedy(items, cap):
    v = 0
    for w, val in sorted(items, key=lambda it: it[1] / it[0], reverse=True):
        if w <= cap:
            cap -= w
            v += val
    return v

def knap_dp(items, cap):
    dp = [0] * (cap + 1)
    for w, val in items:
        for c in range(cap, w - 1, -1):
            if dp[c - w] + val > dp[c]:
                dp[c] = dp[c - w] + val
    return dp[cap]

print(str(knap_greedy([(6, 30), (5, 20), (5, 20)], 10)) + "/" + str(knap_dp([(6, 30), (5, 20), (5, 20)], 10)))