数组优化(DP + 贪心)

因为问题是求个数, 因此, 1个低面值和1个高面值对个数的贡献都是1.
因此, 优先拼出低面值是可以的.
dp[j]: True or False, 表示当前j面值是否已经被拼出来了.
used[j]: 当从小到大, 扫描到面值j时, 当前面值的硬币被使用了多少个了.

面值从低到高进行扫描, 如果发现dp[j] == False, 并且dp[j - a] == True, 并且used[j - a] < c, 即, a面值的硬币还没有被用完, 那么, 面值j应该被优先拼出来.

数组优化算法貌似只适用于计数类的”多重背包问题”, 不适用于求最值的”多重背包问题”.

时间复杂度

O(N * M)

Python 代码

while True:
    N, M = map(int, input().split())
    if N == 0 and M == 0:
        break
    dp = [False] * (M + 1)
    dp[0] = True
    ans = 0
    L = list(map(int, input().split()))
    n = len(L) // 2
    A = L[:n]
    C = L[n:]
    for i in range(N):
        used = [0] * (M + 1)
        a = A[i]
        c = C[i]
        for j in range(a, M + 1):
            if not dp[j] and dp[j - a] and used[j - a] < c:
                dp[j] = True
                used[j] = used[j - a] + 1
                ans += 1
    print(ans)