背包问题

在背包的容量下，最多能装多大价值

0-1背包问题：每件物品最多只用一次

完全背包：每件物品可用无限次

多重背包：每件物品都有Si个

分组背包：每一组物品中最多只能挑选一个物品

0-1背包

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 ii 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

输入格式

第一行两个整数N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi, wi，用空格隔开，分别表示第 i件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000 0<vi,wii≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

n, v = [int(x) for x in input().split(" ")]
f = [[0] * (n + 1 + v) for _ in range(n + 1 + v)]
ws = [0] * (n + 1)
vs = [0] * (n + 1)

for i in range(1, n + 1):
    vs[i], ws[i] = [int(x) for x in input().split(" ")]

for i in range(1, n + 1):
    for j in range(0, v + 1):
        f[i][j] = f[i - 1][j]
        if j >= vs[i]:
            f[i][j] = max(f[i][j], f[i - 1][j - vs[i]] + ws[i])
print(f[n][v])

n, v = [int(x) for x in input().split(" ")]
f = [0] * (n + 1 + v)
ws = [0] * (n + 1)
vs = [0] * (n + 1)

for i in range(1, n + 1):
    vs[i], ws[i] = [int(x) for x in input().split(" ")]

for i in range(1, n + 1):
    for j in range(v, vs[i] - 1, -1):
        f[j] = max(f[j], f[j - vs[i]] + ws[i])
print(f[v])

完全背包问题

有 N 种物品和一个容量是 V的背包，每种物品都有无限件可用。

第 i种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

输入格式

第一行两个整数N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N行，每行两个整数 vi，wi，用空格隔开，分别表示第 ii 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000 0<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

n, v = [int(x) for x in input().split(" ")]
f = [[0] * (n + 1 + v) for _ in range(n + 1 + v)]
vi = [0] * (n + 1)
wi = [0] * (n + 1)

for i in range(1, n + 1):
    vi[i], wi[i] = [int(x) for x in input().split(" ")]

# 从前i可物品中选
for i in range(1, n + 1):
    for j in range(v + 1):
        # f[i][j] = f[i - 1][j]
        for k in range(j + 1):
            if j < vi[i] * k:
                break
            f[i][j] = max(f[i][j], f[i - 1][j - vi[i] * k] + wi[i] * k)

print(f[n][v])

# 注意数据加强后朴素做法已经不能过了

n, v = [int(x) for x in input().split(" ")]
f = [[0] * (n + 1 + v) for _ in range(n + 1 + v)]
vi = [0] * (n + 1)
wi = [0] * (n + 1)

for i in range(1, n + 1):
    vi[i], wi[i] = [int(x) for x in input().split(" ")]

# 从前i可物品中选
for i in range(1, n + 1):
    for j in range(v + 1):
        f[i][j] = f[i - 1][j]
        if j >= vi[i]:
            f[i][j] = max(f[i][j], f[i][j - vi[i]] + wi[i])
print(f[n][v])

image-20200716230456717

n, v = [int(x) for x in input().split(" ")]
f = [0] * (v + 1)
vi = [0] * (n + 1)
wi = [0] * (n + 1)

for i in range(1, n + 1):
    vi[i], wi[i] = [int(x) for x in input().split(" ")]

# 从前i可物品中选
for i in range(1, n + 1):
    for j in range(vi[i], v + 1):
        f[j] = max(f[j], f[j - vi[i]] + wi[i])
print(f[v])

多重背包

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100 0<vi,wi,si≤100

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

n, v = [int(x) for x in input().split(" ")]

vi = [0] * (n + 1)
wi = [0] * (n + 1)
si = [0] * (n + 1)

f = [[0] * (n + 1 + v) for _ in range(n + 1 + v)]

for i in range(1, n + 1):
    vi[i], wi[i], si[i] = [int(x) for x in input().split(" ")]

for i in range(1, n + 1):
    for j in range(v + 1):
        for k in range(si[i] + 1):
            if j < vi[i] * k:
                break
            f[i][j] = max(f[i][j], f[i - 1][j - vi[i] * k] + wi[i] * k)
print(f[n][v])

二进制优化多重背包

数据范围

0<N≤1000 0<V≤2000 0<vi,wi,si≤2000

from math import log2

n, v = [int(x) for x in input().split(" ")]
xx = n * (int(log2(v)) + 1)
vi = [0] * xx
wi = [0] * xx

dp = [0] * (v + 1)

cnt = 0
for _ in range(n):
    a, b, c = [int(x) for x in input().split(" ")]
    k = 1
    while c >= k:
        cnt += 1
        vi[cnt] = k * a
        wi[cnt] = k * b
        c -= k
        k *= 2
    if c > 0:
        cnt += 1
        vi[cnt] = c * a
        wi[cnt] = c * b

for i in range(1, cnt + 1):
    for j in range(v, -1, -1):
        if j < vi[i]:
            break
        dp[j] = max(dp[j], dp[j - vi[i]] + wi[i])
print(dp[v])

单调队列优化多重背包

n, m = [int(x) for x in input().split(" ")]
q = [[0, 0] for _ in range(m + 1)]  # (pos, val)
dp = [0] * (m + 1)

for _ in range(n):
    v, w, s = [int(x) for x in input().split(" ")]
    for j in range(v):
        hh, tt, stop = 0, 0, (m - j) // v

        for k in range(stop + 1):
            val = dp[k * v + j] - k * w

            while hh < tt and val >= q[tt - 1][1]:
                tt -= 1

            q[tt][0] = k
            q[tt][1] = val
            tt += 1

            if q[hh][0] < k - s:
                hh += 1

            dp[v * k + j] = q[hh][1] + k * w

print(dp[m])

混合背包

有 N种物品和一个容量是 V 的背包。

物品一共有三类：

• 第一类物品只能用1次（01背包）；

• 第二类物品可以用无限次（完全背包）；

• 第三类物品最多只能用 si次（多重背包）；

每种体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 NN 行，每行三个整数 vi,wi,si用空格隔开，分别表示第 i 种物品的体积、价值和数量。

• si=−1表示第 i 种物品只能用1次；

• si=0 表示第 i 种物品可以用无限次；

• si>0 表示第 i 种物品可以使用 si 次；

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000 0<vi,wi≤1000 −1≤si≤1000

输入样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例：

8

from math import log2

n, m = [int(x) for x in input().split()]

f = [0] * (m + 1)

xx = n * (int(log2(m)) + 1)
a = [0] * xx
b = [0] * xx
c = [False] * xx  # False: 完全背包，True 0-1背包

index = 0

for _ in range(n):
    v, w, s = [int(x) for x in input().split()]
    if s == 0:
        a[index] = v
        b[index] = w
        index += 1
    else:
        if s == -1:
            s = 1
        k = 1
        while k <= s:
            a[index] = k * v
            c[index] = True
            b[index] = k * w
            index += 1
            s -= k
            k <<= 1

        if s:
            a[index] = s * v
            c[index] = True
            b[index] = s * w
            index += 1

for i in range(index):
    if c[i]:
        for j in range(m, a[i] - 1, -1):
            f[j] = max(f[j], f[j - a[i]] + b[i])
    else:
        for j in range(a[i], m + 1):
            f[j] = max(f[j], f[j - a[i]] + b[i])

print(f[m])

二维费用的背包

n, v, m = [int(x) for x in input().split()]

dp = [[0] * (m + 1) for _ in range(v + 1)]

for _ in range(n):
    a, b, c = [int(x) for x in input().split()]
    for j in range(v, a - 1, -1):
        for k in range(m, b - 1, -1):
            dp[j][k] = max(dp[j][k], dp[j - a][k - b] + c)

print(dp[v][m])

分组背包

分组背包问题目前还没有看见有优化版本，多是朴素做法

有 N组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 v[i][j]，价值是 w[i][j]，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 NN 组数据：

• 每组数据第一行有一个整数 S[i]，表示第 i 个物品组的物品数量；

• 每组数据接下来有 Si 行，每行有两个整数v[i][j] w[i][j]，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100 0<S ≤ 100 0<v[i][j], w[i][j] ≤100

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例：

8

n, v = [int(x) for x in input().split(" ")]
vi = [[0] * (n + 1 + v) for _ in range(n + 1)]
wi = [[0] * (n + 1 + v) for _ in range(n + 1)]
si = [0] * (n + 1)
f = [0] * (v + 1)

for i in range(1, n + 1):
    si[i] = int(input())
    for j in range(si[i]):
        vi[i][j], wi[i][j] = [int(x) for x in input().split(" ")]

for i in range(1, n + 1):
    for j in range(v, -1, -1):
        for k in range(si[i]):
            if vi[i][k] > j:
                continue
            f[j] = max(f[j], f[j - vi[i][k]] + wi[i][k])

print(f[v])