01 Backpack Problem

Topic describes

There are N items and a backpack of capacity V. You can only use each item once.

The ith item has volume v nu I and value W nu I.

Solve which items to put into the backpack so that the total volume of these items does not exceed the backpack capacity, and the total value of the maximum. Output maximum value.

Input format

In the first line, two integers, N and V, separated by Spaces, represent the number of items and the volume of the backpack respectively.

Then there are N rows, each with two integers v I,w I, separated by Spaces, for the ith

The size and value of an item.

The output format

Output an integer representing the maximum value.

Data range

0 < N, V 1000 or less

0 is less than v I,w I is less than 1000

Enter the sample

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

Example output:

8

Dynamic programming

Parameter definition:

• Nitems
• VThe total capacity of the backpack
• CiIn the firstiThe cost of an item
• WiIn the firstiThe value an item gets

Define state

F[I,V]F[I,V]F[I,V] indicates that the item whose total weight does not exceed VVV among the first three items can maximize the total value, where 1≤ I ≤N1≤ I ≤ I ≤N.

For item III, there are two possibilities: put it in or not put it in

• If the ith item is not added, the backpack capacity remains unchanged and the problem becomes F[I −1,V]F[i-1,V]F[I −1,V]

• When the ith item is put in, the backpack capacity decreases and the problem becomes F[I −1,V−Ci]+WiF[I-1, V-CI]+WiF[I −1,V−Ci]+Wi,

  Since the i-th item has been put into the backpack, the value obtained is Wi, leaving only V−Ci for the previous I-1 item

The best solution is to compare which of the two options is better,

Transfer equation

$F[i,v]=max(F[i-1,v],F[i-1,v-Ci]+Wi)$

The initial state of the boundary condition is zero means that nothing is loaded

Code implementation

Python

Two-dimensional DP

N,V = map(int, input().split())

dp = [[0]*(V+1) for _ in range(N)]

for i in range(N):
    vi, wi = map(int, input().split())
    for j in range(V, vi-1, -1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-vi]+wi)
print(dp[-1][-1])
Copy the code

Time complexity O(NV)O(NV)O(NV)

Space complexity O(NV)O(NV)O(NV)

Spatial optimization – one-dimensional DP

V,N = map(int.input().split())

dp = [0] * (V + 1)
for i in range(N):
    # print(i)
    vi, wi = map(int.input().split())
    for j in range(V, vi - 1, -1):
        dp[j] = max(dp[j], dp[j - vi] + wi)
print(dp[-1])

Copy the code

Time complexity O(NV)O(NV)O(NV)

Space complexity O(V)O(V)O(V)