Foreword
For students who learn algorithms, dynamic programming is one of the more important problems they must learn; the 0-1 knapsack problem is the most classic dynamic programming problem; this blog also mainly uses dynamic programming to solve the 0-1 knapsack problem .
Problem Description
There are the following backpack weights and their corresponding masses. The maximum load-bearing weight of the backpack is 6kg. How to load the backpack to maximize the mass of the items within the maximum weight-bearing range?
| Item number | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Weight | 3kg | 1kg | 2kg | 4kg |
| Quality | 6￥ | 10￥ | 5￥ | 10￥ |
Dynamic programming for problem analysis
First, we create an array of dp[i][j], bag[index] array represents the weight and quality of items;
( bag[index][0] means weight, bag[index][1] means mass); i means items, j means the maximum weight that the current backpack can bear; dp[i][j] means current The maximum mass that the backpack can hold when its weight is j. At this time, we can wait for a dynamic transfer equation:
| dp[i][j] = max(dp[i-1][j], dp[i-1][j-bag[index][0]]+bag[index][1]) |
|---|
Equation analysis; when we go to traverse items, we will be divided into two situations, namely loading and not loading;
Do not load the item: the mass of dp[i][j] is the mass of the previous item, which is equal to dp[i-1][j]; i represents the item, which is the mass of i-1.
Load the item: dp[i-1][j-bag[index][0]]+bag[index][1], i represents the current i-th item, i-1 represents the previous item, because j Indicates the maximum mass that the current backpack can carry, so j-bag[index][0] means that if you want to load an item, then the maximum capacity of the backpack that must take an item (i.e. the i-1th item) is j- bag[index][0], because the i-th item is just filled with the backpack with capacity j.
Code resolution
| bag, n, dp = [[6,3],[10,1],[5,2],[10,4]], 6, []# bag represents the weight of the item and its corresponding mass, n is For i in range(len(bag)): dp.append([0]*(n+1)) for i in range(n+1): if i >= bag[0][1]: dp[0][i] = bag[0][0] #The maximum mass corresponding to the first item will be obtained by traversing the array for the first time for i in range(1,len(bag)): for j in range(n+1): if bag[i][1] <= j: dp[i][j] = max(dp[i-1][j], dp[i-1][j-bag[ i][1]]+bag[i][0]) # Take the current maximum mass of dp[i][j] print(dp[-1][-1]) # Print the final dp j=n (the largest backpack Capacity) maximum quality |
|---|
to sum up
This blog mainly describes how to use dynamic programming to solve the 0-1 knapsack problem; in general, the 0-1 knapsack problem is a classic dynamic programming problem, and the dp array is used to memorize the required values to derive the related next one Value.
Recommended Posts