dp = [0] * (W + 1)
for w_i, v_i in items:
for w in range(W + 1, w_i - 1, -1):
dp[w] = max(dp[w], dp[w - w_i] + v_i)
answer = max(dp)
dp = [0] * (W + 1)
for w_i, v_i in items:
for w, dp_w in zip(range(W + 1, w_i - 1, -1), reversed(dp)):
if (v := dp[w - w_i] + v_i) > dp_w:
dp[w] = v
answer = max(dp)
dp = [0] * (W + 1)
for w_i, v_i in items:
for w, dp_w, dp_p in zip(range(W + 1), dp, dp[w_i:]):
if dp_p + v_i > dp_w:
dp[w] = dp_p + v_i
answer = max(dp)
dp = {0: 0}
for w_i, v_i in items:
dp_update = {}
for w, v in dp.items():
if w + w_i <= W and v + v_i > dp.get(w + w_i, 0):
dp_update[w + w_i] = v + v_i
dp.update(dp_update)
answer = max(dp.values())
answer = min(answer, min(dp[-w_i:]) + v_i)
0-1 knapsack
V합의 최댓값 V합의 최솟값
합이 W 이하일때 16493 합이 정확히 W일때 22115 (v는 모두 1) 합이 W 이상일때 23748
Unbounded
V합의 최댓값 V합의 최솟값 가능한 조합의 가짓수
합이 W 이하일때 합이 정확히 W일때 Minimum coin change problem Coin Change Problem 합이 W 이상일때 1106
def count_subset(nums, target):
first, second = nums[: len(nums) // 2], nums[len(nums) // 2 :]
first_sums, second_sums = [0], [0]
for num in first:
first_sums.extend([num + x for x in first_sums])
for num in second:
second_sums.extend([num + x for x in second_sums])
second_counter = collections.Counter(second)
ret = sum(second_counter[target - x] for x in first_sums)
if target == 0:
ret -= 1
return ret
def count_subset2(nums, target):
first, second = nums[: len(nums) // 2], nums[len(nums) // 2 :]
first_sums = [0]
for num in first:
first_sums.extend([num + x for x in first_sums])
counter = collections.Counter(first_sums)
second_sums_iter = subsets(second, 0, lambda s, num: s + num)
ret = sum(counter[target - x] for x, _ in second_sums_iter)
if target == 0:
ret -= 1
return ret
9084 (=3067):Coin Change Problem