01 Backpack
Problem solving
- This problem cannot be solved with greed. For example, in example 2, if you use greedy thinking, you should install the first item first, so you can't install other items, and you can only get a value of 15. Greedy problem here
- It is agreed that f[i][j] represents the maximum total value that can be obtained by putting the first I items - > backpack with capacity of j
- If j < w [i], the i-th item cannot be loaded. At this time, it is equivalent to the first i - 1 item - > backpack with capacity of j,
f[i][j] = f[i - 1][j] - If J > = w [i], it can hold the ith item. If you choose to load the i-th item, its value is v[i], and the remaining capacity of the backpack is j - w[i], then the maximum value obtained from the first I-1 item - > the backpack with the capacity of j - w[i] is f[i - 1][j - w[i]] + v[i]. The best result of comparing loading and not loading is:
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]) - The maximum total value of n items - > backpack with capacity of m is f[n][m]
This is the complete code
#include <bits/stdc++.h>
using namespace std;
int m, n;
int w[39], v[39];
int f[39][209];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i ++) {
cin >> w[i] >> v[i];
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if (j < w[i]) {
f[i][j] = f[i - 1][j];
}
else {
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
}
}
}
cout << f[n][m];
return 0;
}
optimization
- and Previous article The optimization idea of this article is the same. Let's take a look at the following core statement to see how to compress the two-dimensional array f into a one-dimensional array
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]) - The two-dimensional array f is regarded as a matrix with n rows and m columns. The cyclic variable i is from small to large. The elements of row i can be recursively calculated by the elements of row i - 1
- The item f[i - 1][j - w[i] on the right side of the assignment statement is on the left side of column j. therefore, when compressed into a one-dimensional array, the cyclic variable j must cycle from large to small to avoid the influence of the updated element on the next assignment statement
- Another statement f[i][j] = f[i - 1][j], when compressed into a one-dimensional array, becomes f[j] = f[j], which can be omitted
- The maximum total value of n items - > backpack with capacity of m is f[m]
The space complexity of the optimized code is o(n)
#include <bits/stdc++.h>
using namespace std;
int m, n;
int w[39], v[39];
int f[209];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i ++) {
cin >> w[i] >> v[i];
}
for (int i = 1; i <= n; i ++) {
for (int j = m; j >= w[i]; j --) {
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
}
cout << f[m];
return 0;
}
Container loading
In addition to the idea of the above question, this question has another idea
Problem solving
- If the weight j can be calculated from the first i items, set f[j] to true; If not, set f[j] to false.
- If the weight j is added up because the i-th item is selected, the first I-1 item must be able to add up the weight j - w[i], so:
f[j] = f[j] | f[j - w[i]] - During initialization, you need to set f[1] ~ f[m] to false, because these weights have not been rounded up; And f[0] should be set to true, because when no item is selected, the weight is 0
- Finally, to find the maximum weight of n items - > backpack with capacity of M, j should be enumerated from m to 1. If f[j] == true, it means that weight j can be obtained. There is no need to continue enumeration, and the program ends
This is the complete code
#include <bits/stdc++.h>
using namespace std;
int n, m;
int w[10009];
bool f[40000];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> w[i];
f[0] = true;
for (int i = 1; i <= n; i ++) {
for (int j = m; j >= w[i]; j --) {
f[j] |= f[j - w[i]];
}
}
for (int j = m; j >= 1; j --) {
if (f[j] == true) {
cout << j;
return 0;
}
}
return 0;
}
Another angle
- If f[j] == true before loading the i-th item, you can get the weight of j + w[i] after loading the i-th item
- The premise of this recurrence is that the weight before loading the ith item cannot exceed m - w[i], otherwise it will exceed the capacity of the backpack
Remember this idea. This method will be used in the following topics
#include <bits/stdc++.h>
using namespace std;
int n, m;
int w[10009];
bool f[40000];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> w[i];
f[0] = true;
for (int i = 1; i <= n; i ++) {
for (int j = m - w[i]; j >= 0; j --) {
if (f[j]) {
f[j + w[i]] = true;
}
}
}
for (int j = m; j >= 1; j --) {
if (f[j] == true) {
cout << j;
return 0;
}
}
return 0;
}