Dynamic programming 01 knapsack and complete knapsack

Catalog

One 、01 knapsack

Problem description ：

Their thinking ：

Two 、 Completely backpack

Problem description ：

Their thinking ：

---

One 、01 knapsack

Problem description ：

There's a backpack , The total carrying capacity of the backpack is Wkg, Yes n Items （ There is only one thing for each item ）, The weight of each item varies , And indivisible . On the premise of not exceeding the weight of the backpack , How to maximize the total weight of items in the backpack ？

So it's called 01 Backpack is because items can be packed （ It can only be loaded with 1 Time ） Or not （0）.

Their thinking ：

Using the idea of dynamic programming , hypothesis dp[i][j] Before presentation i Items backpack capacity is j The maximum weight that can be loaded under the condition of ,v[i] It means the first one i The value of items ,w[i] It means the first one i The weight of each item , be

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) （i = 0, 1, ..., n; j = 0, 1, ... , W）

among dp[i - 1][j] It's the second i The total value of items not put in the backpack ,dp[i - 1][j - w[i]] + v[i] Is the total value of the current item in the backpack ; The reference code is ：

dp[0][0] = 0;
for (int i = 1; i <= n; i++) { 
	for (int j = W; j >= w[i]; j--) {
      dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
   }
}

Usually, two-dimensional arrays can also be optimized into one-dimensional arrays , namely dp[j] = max(dp[j], dp[j - w[i]] + v[i])（i = 0, 1, ..., n; j = 0, 1, ..., W）

But at this time, it is required max Function dp[j] Must be The value of the previous state , Then cover with the maximum dp[j], So at this time, the inner circulation should The reverse ：

dp[0] = 0;
for (int i = 1; i <= n; i++) { 
	for (int j = W; j >= w[i]; j--) {
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
   }
}

Two 、 Completely backpack

Problem description ：

Complete backpack with 01 The difference between backpacks is that each item has more than one , It is Countless pieces .

Their thinking ：

For the number of single items , We can adopt the idea of greedy algorithm , The maximum weight limit of the backpack is not exceeded w that will do , So the maximum quantity of each item is W/c[i] The value of rounding down , At this point, the state transition equation becomes ：

dp[i][j] = max(dp[i - 1][j - k * w[i]] + k * v[i]) (i = 0, 1, ..., n; j = 0, 1, ..., W; k = 0, 1, 2, ..., W/c[i])

The reference code is ：

dp[0][0] = 0;
int maxtemp = 0;
for (int i = 1; i <= n; i++) { 
	for (int j = w[i]; j <= W; j++) {
      for (int k = 1; k <= W / w[i]; k++) 
          maxtemp = max(maxtemp, dp[i - 1][j - k * w[i]] + v[i]);
      dp[i][j] = max(maxtemp, dp[i][j]);
   }
}

Convert to a one-dimensional array ：dp[j] = max(dp[j], dp[j- w[i]] + v[i]), The code at this time is ：

dp[0] = 0;
for (int i = 1; i <= n; i++) { 
	for (int j = w[i]; j <= W; j++) {
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
   }
}

The inner circulation at this time is The order Of , therefore dp[j] It represents the maximum value of the current state , It can be seen from the state transition equation of two-dimensional array , The complete knapsack does not need to be compared with the self value of the previous state , So it's sequential .