Dynamic Programming: 01 Backpack, Complete Backpack, Multiple Backpack, 01 Backpack Combination, Complete Backpack Combination & Alignment Problems

 
 Suggested music to listen to before studying: your backpack 🎒~

⭐🚂⭐General Template for Backpacking Issues：

[Note: This general template as a summary of things, the first backpack problem to understand before looking at a lot of clarity. Of course, sometimes the template formula should be modified according to the actual problem.
 
1️⃣ Internal and External Circulation Classification:

2️⃣ Problem Categorization:

 
 

⭐ The following specific explanations of each backpack issue are in the code comments.

 

🚀I.01 backpack issues:

 The 01 backpack is arguably the foundation for all other backpack issues and must be figured out thoroughly!

 First, let's look at the writing of a two-dimensional dp array; just read the comments for the exact explanation:
[Note: The following is to traverse the item first and then the backpack, so it will be better to understand. Of course, traversing the backpack first, and then traversing the items, is also possible! Because from the state transfer formulas of these two cases, we can see (the state transfer formulas of these two cases are the same, but the order of the for loops is just switched), the updated data come from the left and up directions. Of course, in some backpacking problems, the order of the two for loops is often very important].

def bag_01_2D():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bag_weight = 4

    #State Definition:dp[i][j] denotes the maximum value of selecting items from 0-i items up to j weight.
    #Note the way two-dimensional arrays are created in python
    dp = [[0]*(bag_weight+1) for _ in range(len(weight)+1)]

    #Boundaries:
    # The first column is all zeros, because the value is zero (since the initialization is all zeros it's not needed here).
    # The first line indicates that the maximum value of item 0 is selected only (to satisfy that the backpack capacity is sufficiently small to accommodate item 0).
    for j in range(bag_weight, weight[0]-1, -1):
        dp[0][j] = dp[0][j - weight[0]]+value[0]

    # Outer loop to traverse items
    for i in range(1, len(weight)):
        # Iterate through the backpack capacity in an inner loop
        for j in range(0, bag_weight+1):
            # The capacity of the backpack does not allow for the ith item
            if j < weight[i]:
                dp[i][j] = dp[i-1][j]

            # i item that fits in the backpack's capacity, with or without a bag
            # Not put: that would be equal to the maximum value of the first i-1 items (in capacity j)
            # put: that equals the maximum value of the first i-1 items (in capacity j-weight[i]) + the value of the ith item
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])

    return dp[len(weight)-1][bag_weight]

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30

[dp[i-1][j-weight[i]]+value[i] means: item i is included when the weight is j, then surely you have to punch the weight j-weight[i] to transfer over ah come on].
 This is because it is clear from the state transfer equation that moment i is only related to the previous moment i-1. So you can just use a one-dimensional array instead of a two-dimensional array for scrolling. The other two backpack problems use one-dimensional arrays, after all, the space complexity is small.
 An example explanation of the reverse order of the inner loop (because this avoids the positive order when the previous state picks item i and the later state picks item i again based on it, which can only be picked once. So the reverse order traversal ensures that the item is picked only once):

def bag_01():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bag_weight = 4

    # dp[j] denotes the maximum value of things that can be put in a backpack of capacity j
    dp = [0]*(bag_weight+1)

    # Outer loop traversing items
    for i in range(0, len(weight)):
        # Inner loop traverses the backpack capacity, always in reverse order!!!! This ensures that item i is only put in once
        # From the two-dimensional that equation we know that the current moment i is only related to the state at moment i-1.
        # If positive order then, when updating dp[j] for the current moment i in one dimension, dp[j-weight[i]] becomes updated for the current moment i, and what's needed at that point is the old value of dp[j-weight[i]] from the previous moment i-1 (which is updated first thanks to the reverse order traversal)
        # So the reverse order prevents the old value of dp[j-weight[i]] from being updated first.
        for j in range(bag_weight, weight[i]-1, -1):
            # Above the two-dimensional approach: if j < weight[i] and else here to the following sentence, because meet the if is equal to the state of the moment i-1, here unchanged or d[j] that is, the state of the moment i-1, so you can not write. And for loop control j will not be less than the weight [i], less than the weight [i] do not have to update on the good, along with the moment of i-1 on the OK.
            #No or ith item
            # not put: then it is the maximum value when taking the first i-1 items (in capacity j)
            # put: then the maximum value of the first i-1 items (in capacity j-weight[i]) is taken
            dp[j] = max(dp[j], dp[j-weight[i]]+value[i])

    return dp[bag_weight]

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

 So can the two inner and outer for loops above be switched? (i.e. iterate over the backpack capacity before iterating over the items?)
 A: Definitely not, because the traversal of the capacity of the backpack is in reverse order (so that the indexes of d[j] that are less than j are all 0, they are all still initialized state). Look at the state transfer formula can be known, so that the consequence is that each backpack only one item hahaha.

 And 2D doesn't use reverse order because:
 Since for a two-dimensional dp, dp[i][j] are computed through the previous layer, i.e., dp[i - 1][j] (since item i was not taken at i-1, the reason for the inverse order is to avoid that item i was taken repeatedly in the current layer), the dp[i][j] of the current layer is not overwritten!

 

🚀II. Complete backpack problem:

 It is to change the inner loop in the 01 backpack into a positive order traversal, you can realize that each item can be selected an infinite number of times. (As for why the positive order, understand the previous 01 backpack of the reverse order of the explanation of this will be very good to understand):

# State Definition:dp[i][j] denotes the maximum value of selecting items from 0-i items up to j weight.

# 01 backpack with state transfer: max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
# And in a complete knapsack, the state transfer is: max(dp[i-1][j], dp[i][j-weight[i]]+value[i]), see below for an explanation.


def bag_full():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bag_weight = 4

    # dp[j] denotes the maximum value of items that can be put down in a backpack of capacity j
    dp = [0]*(bag_weight+1)

    # Outer loop traversing item types
    for i in range(0, len(weight)):
        # Inside loop traverses the backpack capacity, in positive order, as it can be put repeatedly
        for j in range(weight[i], bag_weight+1):

            # The next i item in the backpack's capacity, with or without it.
            # Do not put: then it is equal to the maximum value of the first i-1 items (in capacity j)
            # put: that is equal to the maximum value of the first i items (in capacity j-weight[i]).
            # The choice of placement does not depend on the state of the previous moment, since the previous moment contains only i-1 items and not the ith item, so it is not possible to transfer from the i-1 moment.

            dp[j] = max(dp[j], dp[j-weight[i]]+value[i])

    return dp[bag_weight]

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27

 2 more soul tortures to completely and utterly figure out the full backpack.
 1. Can the order of the inner and outer for loops be reversed?
 It doesn't matter if you can, the code is as follows, with the state transfer equations unchanged.

	for j in range(0, bag_weight+1):
		for i in range(0, len(weight)):
			if weigth[i]<=j:
				dp[j] = max(dp[j], dp[j-weight[i]]+value[i])

• 1
• 2
• 3
• 4

 Because dp[j] is calculated based on the dp[j] before subscript j. Just make sure that dp[j] before subscript j is calculated, after all, positive order traversal, you can select countless items haha.

 2. How about a 2-dimensional array implementation?
 The state transfer equation in the 01 backpack 2D dp array realization is:

# i item that fits in the backpack's capacity, with or without a bag
# Not put: that would be equal to the maximum value of the first i-1 items (in capacity j)
# put: that is equal to the maximum value of the first i-1 items (in capacity j-weight[i])
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])

• 1
• 2
• 3
• 4

 The state transfer equation is changed to in the complete backpack 2D array implementation:

# The next i item in the backpack's capacity, with or without it.
# Do not put: then it is equal to the maximum value of the first i-1 items (in capacity j)
# put: that is equal to the maximum value of the first i items (in capacity j-weight[i]).
#Choice of release does not depend on the state of affairs with the previous moment.
# Since the previous moment contains only i-1 items and not the ith item, it is not possible to transfer from the i-1 moment.
dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]]+value[i])

• 1
• 2
• 3
• 4
• 5
• 6

 I've heard that those variant questions will have a big difference in the order of the two for loops, so it's crucial to pay attention to the questions with a slight change in the order of the for loops. (Because the order of the two for loops will be switched in some problems will involve combinations or permutations of problems, so sometimes can not be switched, depending on the problem. Only purely complete backpack type problems can be switched.)
 For the backpack problem, the recursive formula is kind of easy, the hard part is in the traversal order, and if you get the traversal order right, then you've really sorted it out.

 

🚀III. Multiple backpack issues:

def bag_multi():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    limit = [2,2,1]
    bag_weight = 4

    # dp[j] denotes the maximum value of items that can be put down in a backpack of capacity j
    dp = [0]*(bag_weight+1)

    # Outer loop traversing item types
    for i in range(0, len(weight)):
        # inner loop traversing the backpack capacity, in reverse order, because I see it as a :01 backpack problem
        # Why can I see the 01 backpack problem. Because it's the equivalent of me bundling various numbers of items in each category to see a whole, which can only be selected once (provided of course that it also doesn't exceed the capacity of the backpack :j)
        # The specific action is to open an additional loop within the inner loop and iterate through each bundle case that satisfies the condition to see which bundle case has the largest value.
        for j in range(bag_weight, weight[i]-1, -1):
            k=1
            while(k<=limit[i] and k*weight[i]<=j):
                dp[j] = max(dp[j], dp[j-k*weight[i]] + k*value[i])
                k += 1

    return dp[bag_weight]

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21

 Another way that has the same time complexity but space can be a bit wasted is:
 Think of each type of item as an item that can only be selected 1 time, expand the WEIGHT and VALUE lists a bit, and then it's straightforward to think of it as a 01 backpack problem.
 Then there is a binary idea to optimize the time complexity of the specific method of their own Baidu. Because I heard that leetcode does not have multiple backpacks type of questions, the interview will also be less. It's basically a variant of the 01 backpack or complete backpack type of topic.

 

🚀IV.01 Backpack Problems:

def bag_01_exist():
    weight = [1, 3, 4, 2, 2]
    bag_weight = 13

    # Can dp[j] just fill up a backpack of capacity j
    dp = [False]*(bag_weight+1)
    # dp[j] are all updated relying on the dp value of the index before j. If dp[0]=False. then the whole dp array is False.
    dp[0] = True

    # Outer loop traversing items
    for i in range(0, len(weight)):
        # Inner loop traverses backpack capacity, reverse order is the same as for 01 backpacks
        for j in range(bag_weight, weight[i]-1, -1):

            # In the i-1 state, dp[j] indicates whether the selection of items from the first i-1 items can just fill up the backpack with capacity j
            #dp[j-weight[i]] indicates whether selecting items from the first i items will just fill the backpack with capacity j when the backpack capacity is j-weight[i].
            # So one of the above two cases will satisfy True, then surely dp[j] is True
            dp[j] = dp[j] or dp[j-weight[i]]

    return dp[bag_weight]

print(bag_01_exist())

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

 

🚀V. Problems with complete backpacks:

def bag_full_exist():
    weight = [3,11,12,15]
    bag_weight = 10

    # Can dp[j] just fill up a backpack of capacity j
    dp = [False]*(bag_weight+1)
    # dp[j] are all updated relying on the dp value of the index before j. If dp[0]=False. then the whole dp array is False.
    dp[0] = True

    # Iterate through each item in an outer loop
    for i in range(0, len(weight)):
        # Inner loop to traverse the pack capacity, in positive order
        for j in range(weight[i], bag_weight+1):

            # In the i-1 state, dp[j] indicates whether the selection of items from the first i-1 items can just fill up the backpack of capacity j
            #dp[j-weight[i]] indicates whether selecting items from the first i items will just fill the backpack of capacity j when the backpack capacity is j-weight[i].
            # So one of the above two cases will satisfy True, then surely dp[j] is True

            dp[j] = dp[j] or dp[j-weight[i]]
    return dp[bag_weight]

print(bag_full_exist())

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

 

🚀VI.01 Backpack combination problem:

 That is, an extension of the 01 backpack problem to find the number of combinations that fill the backpack. Just look at the code for an explanation:

def bag_01_combine():
    weight = [1, 3, 4, 2, 2]
    bag_weight = 4

    # dp[j] means that there are a total of dp[j] combinations for filling a backpack of capacity j
    dp = [0]*(bag_weight+1)

    # i.e. the backpack capacity is 0, there is 1 way i.e. to fit 0 pieces. It can't be initialized to 0 after all as seen from the state transfer formula that
    # dp[j] are updated relying on the dp value of the index before j. If dp[0]=0. then the whole dp array is zero.
    dp[0] = 1

    # Outer loop traversing items
    for i in range(0, len(weight)):
        # Inner loop traverses backpack capacity, reverse order is the same as for 01 backpacks
        for j in range(bag_weight, weight[i]-1, -1):

            # In the i-1 state, dp[j] denotes the number of combinations of items selected from the first i-1 items to fill the backpack capacity of j. Of course the number of combinations is unchanged when I add item i
            #dp[j-weight[i]] denotes the number of combinations of items selected from the first i items to fill the backpack with capacity j when the backpack capacity is j-weight[i].
            # So adding the above two is the following equation, which says: the number of combinations at backpack capacity j is equal to, the number of combinations of the first i-1 items (with backpack capacity j) plus the number of combinations of items selected from the first i items (with backpack capacity j-weight[i])
            dp[j] += dp[j-weight[i]]

    return dp[bag_weight]

print(bag_01_combine())

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24

 

🚀VII. The complete backpack combination problem:

 Figure out 01 backpack combination problem, this is very good to understand, but be careful, the problem of combining the number of inside and outside the 2 for loop can not be reversed, reversed into a combination of the number of or arrangement of the number of problems, which is not the same. This is not the same. Be very careful.

def bag_full_combine():
    weight = [1, 3, 4]
    bag_weight = 4

    # dp[j] means that there are a total of dp[j] combinations for filling a backpack of capacity j
    dp = [0]*(bag_weight+1)

    # i.e. the backpack capacity is 0, there is 1 way i.e. to fit 0 pieces. It can't be initialized to 0 after all as seen from the state transfer formula that
    # dp[j] are updated relying on the dp value of the index before j. If dp[0]=0. then the whole dp array is zero.
    dp[0] = 1

    # Iterate through each item in an outer loop
    for i in range(0, len(weight)):
        # Inner loop to traverse the pack capacity, in positive order
        for j in range(weight[i], bag_weight+1):

            # In state i-1, dp[j] denotes the number of combinations of items selected from the first i-1 items to fill the backpack with item j. Of course, the number of combinations is unchanged when I add item i.
            #dp[j-weight[i]] denotes the number of combinations of items selected from the first i items to fill the backpack with capacity j when the backpack capacity is j-weight[i].
            # So adding the above two is the following equation, which says: the number of combinations at backpack capacity j is equal to the number of combinations of the first i-1 items (with backpack capacity j) plus the number of combinations of items selected from the first i items (with backpack capacity j-weight[i])

            dp[j] += dp[j-weight[i]]

    return dp[bag_weight]

print(bag_full_combine())

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25

⭐The order of the inner and outer for loops is explained below:

 Because traversing the items before traversing the backpack is a combinatorial problem:

for i in range(0, len(weight)):
	for j in range(weight[i], bag_weight+1):
		dp[j] += dp[j-weight[i]]

• 1
• 2
• 3

 Suppose there are two items: weight[0] = 1 and weight[1] = 3. (The goal is to round up to target=4)
 Then you add the 1's to the calculation, then the 3's to the calculation, and the number of methods you get is only the case {1, 3}. and not {3, 1}.
 When for looping though all of the following will happen, leading you to believe that {1, 3} and {3, 1} are counted. You push it through from start to finish. In fact, you'll find that dp[3] in 1 below makes 4 with another 1 (but this 3 is made up of 3 1s), while dp[1] in 2 below makes 4 with another 3 (but this 3 is a 3, not 3 1s). So only cases like 1, 3 will be considered (since the item traversal is placed in the outer layer, the 3 can only appear after the 1!) :

1.   dp[4] += dp[4-1] i.e. dp[4] += dp[3]
2.   dp[4] += dp[4-3] i.e. dp[4] += dp[1]

• 1
• 2

 Hand-calculated once you know, similar reasoning for loop reversal is the arrangement.

 And if you traverse the backpack before traversing the items, it's an alignment problem:

for j in range(0, bag_weight+1):
	for i in range(0, len(weight)):
		if j >= weight[i]: 
			dp[j] += dp[j-weight[i]]

• 1
• 2
• 3
• 4

 Each value of the backpack capacity is computed with 1 and 3, and contains both {1, 3} and {3, 1}.

 If you are looking for the number of combinations it is an outer for loop traversing the items and an inner for traversing the backpack.
 If you are looking for the number of permutations it is an outer for traversing the backpack and an inner for loop traversing the items.

 

🚀VIII. Complete Backpack Alignment Problems:

 That is, you can just switch the position of the for loop, as explained above in the complete backpack combination problem:

def bag_full_permutation():
    weight = [1, 5]
    bag_weight = 6

    # dp[j] means that there are a total of dp[j] combinations for filling a backpack of capacity j
    dp = [0]*(bag_weight+1)

    # i.e. the backpack capacity is 0, there is 1 way i.e. to fit 0 pieces. It can't be initialized to 0 after all as seen from the state transfer formula that
    # dp[j] are updated relying on the dp value of the index before j. If dp[0]=0. then the whole dp array is zero.
    dp[0] = 1

    # Traverse the backpack in an outer loop
    for j in range(0, bag_weight + 1):

        # Iterate over item types in an inner loop
        for i in range(0, len(weight)):
            if j >= weight[i]:
                # In state i-1, dp[j] denotes the number of combinations of items selected from the first i-1 items to fill the backpack with item j. Of course, the number of combinations is unchanged when I add item i.
                #dp[j-weight[i]] denotes the number of combinations of items selected from the first i items to fill the backpack with capacity j when the backpack capacity is j-weight[i].
                # So adding the above two is the following equation, which says: the number of combinations at backpack capacity j is equal to the number of combinations of the first i-1 items (with backpack capacity j) plus the number of combinations of items selected from the first i items (with backpack capacity j-weight[i])
                dp[j] += dp[j-weight[i]]
    return dp[bag_weight]

print(bag_full_permutation())

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24

 
 

⭐This is a Python implementation of the backpack problem, for a java implementation see this:
【1】DP Classic Review: The Backpack Problem

⭐Some reference links:
 This one will explain some variant topics and common templates for backpack problems:
【1】Eat through the backpack problem in one article! (Meticulous introduction + solution template + example analysis + code presentation)
 This and its series of DP articles explain the principles more comprehensively nice:
【2】Dynamic programming: what you should know about the 01 backpack problem!