01 Backpack Problem:
Each item can only be used once
Two-dimensional approach:
#include<iostream>
using namespace std;
const int MAXN = 1005;
int v[MAXN]; // volume
int w[MAXN]; // value
int f[MAXN][MAXN]; // f[i][j], the maximum value of the first i items in volume j
int main()
{
int n, m; //number of items, backpack capacity
scanf("%d%d", & amp;n, & amp;m);
for(int i = 1; i <= n; i + + )
scanf("%d%d", & amp;v[i], & amp;w[i]);//Assign size and value to each item
for(int i = 1; i <= n; i + + ) //i is the current item, there are n items in total
for(int j = 0; j <= m; j + + )//j is the current remaining volume, which must be less than the total volume. The current remaining volume starts from 0, + 1 each time, until there is m volume
{
//The current capacity cannot hold the i-th item, then the value of the current volume is equal to the first i-1 items
if(j < v[i])
f[i][j] = f[i - 1][j];
// It can be installed, but it needs to be judged whether to select the i-th item
else //Judgment method: If you don’t want i item or want i item, but if you want i, just look at the volume of capacity-i, and how much value is contained in the remaining capacity. Compare again whether i is required
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
printf("%d\
",f[n][m]);
return 0;
}
One-dimensional approach:
#include<iostream>
using namespace std;
const int MAXN = 1005;
int v[MAXN]; // volume
int w[MAXN]; // value
int f[MAXN]; // f[j], the optimal solution under backpack capacity j.
int main()
{
int n, m; //number of items, backpack capacity
scanf("%d%d", & amp;n, & amp;m);
for(int i = 1; i <= n; i + + )
scanf("%d%d", & amp;v[i], & amp;w[i]);//Assign size and value to each item
for(int i = 1; i <= n; i + + ) //i is the current item, there are n items in total
for(int j = m; j >=v[i]; j--)//j is the current remaining volume, which must be larger than the size of the item to be operated. The current remaining volume starts from m, and is -1 each time
{
//The current capacity cannot hold the i-th item, then the value of the current volume is equal to the first i-1 items, and the loop will not be entered.
// It can be installed, but it needs to be judged whether to select the i-th item
//Judgment method: The value saved by the capacity of j after traversing to the first i-1 items is compared to the value of the capacity of j-v[i] after traversing to the first i-1 items plus the value of i
//Don't want i item or want i item, but if you want i, just look at the volume of capacity - i, and how much value is contained in the remaining capacity. Compare again whether i is required
//Why does enumerating backpack capacity need to be in reverse order in one dimension?
//In the two-dimensional case, the state f[i][j] is obtained from the state of the previous round i - 1, and f[i][j] and f[i - 1][j] are independent .
//After optimizing to one dimension, if we are still in positive order, then f [smaller volume] is updated to f [larger volume], then it is possible that the state of the i-1th round should be used but the state of the i-1th round is used. The status of the i wheel.
//For example, if the i-th round of the one-dimensional state makes a decision on an item with a volume of 3, then f[7] is updated from f[4], and the correct f[4] here should be f[i - 1][4 ], but f[4] here in enumeration j from small to large becomes f[i][4] in the i-th round of calculation.
//When enumerating backpack capacity j in reverse order, we find that f[7] is also updated by f[4], but because it is in reverse order, f[4] has not been updated from f[7] to f[4]. f[4] has not been calculated in the i-th round, so the actual calculated f[4] at this time is still f[i - 1][4].
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
printf("%d\
",f[m]);
return 0;
}
Complete knapsack problem:
Each item can be used an unlimited number of times
Two-dimensional approach:
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];// f[i][j], the maximum value of the first i items in volume j
int v[N];//volume
int w[N]; // value
int main()
{
int n,m;
scanf("%d%d", & amp;n, & amp;m); //Number of items, backpack capacity
for(int i = 1; i <= n; i + +)//i is the current item, a total of n items
{
scanf("%d%d", & amp;v[i], & amp;w[i]);//Assign size and value to each item
}
for(int i = 1; i<=n;i + +)
for(int j = 0; j<=m;j + +)//j is the current remaining volume, which must be less than the total volume. The current remaining volume starts from 0, + 1 each time
{
//The current capacity cannot hold the i-th item, then the value of the current volume is equal to the first i-1 items
if(j < v[i])
f[i][j] = f[i - 1][j];
else//Whether to select the item
//Don't want i item or want i item, but if you want i, just look at the capacity - the volume of i, how much value is in the remaining capacity, and then compare whether you want i
//If i is not used, the state of i-1 is used. If i is used, the state of i is used, because i can be used infinitely.
f[i][j] = max(f[i - 1][j],f[i][j - v[i]] + w[i]);
}
printf("%d\
",f[n][m]);
return 0;
}
One-dimensional approach:
#include<iostream>
using namespace std;
const int N = 1010;
int f[N];// f[j], the maximum value of the first i items in j volume
int v[N];//volume
int w[N]; // value
int main()
{
int n,m;
scanf("%d%d", & amp;n, & amp;m); //Number of items, backpack capacity
for(int i = 1; i <= n; i + +)//i is the current item, a total of n items
{
scanf("%d%d", & amp;v[i], & amp;w[i]);//Assign size and value to each item
}
for(int i = 1; i<=n;i + +)
//The volume of v[i] is used as the initial volume here, which means that the items in front of i are not looked at, only the items behind i are looked at. But i starts from the first to the nth, so there will be no problem
for(int j = v[i]; j<=m;j + +)//f is the volume of item i. Note that j here is enumerated from small to large, which is different from the 01 backpack
{
//The current capacity cannot hold the i-th item, then the value of the current volume is equal to the first i-1 items, and the loop will not be entered.
// It can be installed, but it needs to be judged whether to select the i-th item
//The value saved by the capacity of j after traversing to the first i item is compared to the value of the capacity of j-k*v[i] after traversing to the first i-1 item plus the value of k*i
//Note that it is traversing to i-1 items, because they may not fit in, so the capacity of j-k*v[i] is not necessarily the value of i-1
//If the size of item i-1 is larger than item i, and its value is less than i, so the latter is smaller
//If the size of item i-1 is smaller than item i, and its value is greater than i, so the latter is larger
f[j] = max(f[j],f[j-v[i]] + w[i]);
}
printf("%d\
",f[m]);
return 0;
}
Multiple Knapsack Problem I:
Each item has different times limit
Two-dimensional approach:
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int v[N];//volume
int w[N]; // value
int s[N];//The number of times this item
int f[N][N];// f[i][j], the maximum value of the first i items in volume j
int n, m;
int main()
{
scanf("%d%d", & amp;n, & amp;m); //Number of items, backpack capacity
for(int i = 1; i <= n; i + + ) //i is the current item, there are n items in total
scanf("%d%d%d", & amp;v[i], & amp;w[i], & amp;s[i]);//Assign size, value and frequency to each item
for(int i = 1; i <= n; i + + )
{
for(int j = 0; j <= m; j + + )//j is the current remaining volume, which must be less than the total volume. The current remaining volume starts from 0, + 1 each time
{
for(int k = 0; k <= s[i] & amp; & amp;k*v[i]<=j; k + + )//Put the item k times until the capacity is not enough or the number of times is reached limit
{
//The value saved by the capacity of j after traversing to the first i item is compared to the value of the capacity of j-k*v[i] after traversing to the first i-1 item plus the value of k*i
//Note that it is traversing to i-1 items, because they may not fit in, so the capacity of j-k*v[i] is not necessarily the value of i-1
//If the size of item i-1 is larger than item i, and its value is less than i, so the latter is smaller
//If the size of item i-1 is smaller than item i, and its value is greater than i, so the latter is larger
//Compare the current value with the value of the previous item plus the value of the current item k times
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
printf("%d\
",f[n][m]);
return 0;
}
One-dimensional approach:
#include<iostream>
using namespace std;
const int N = 12010, M = 2010;
int n, m;
int v[N];//volume
int w[N]; // value
int f[M]; // f[j], the maximum value of the first i items in volume j
int main()
{
scanf("%d%d", & amp;n, & amp;m); //Number of items, backpack capacity
int cnt = 0; //grouping group
for(int i = 1;i <= n;i + + )
{
int a,b,s;
scanf("%d%d%d", & amp;a, & amp;b, & amp;s);//The volume, value and quantity of the i-th item.
int k = 1; // Number of items in the group
while(k<=s)//The number in the group must be less than or equal to the number it has
{
cnt + + ; //Group is added first: 1 2 4 8 16 32 64 128...
v[cnt] = a * k; //Overall volume: volume of the item * number of items
w[cnt] = b * k; // Overall value: value of the item * number of items
s -= k; // s needs to be reduced, k is used, how many are left, this is the content of the group: 7 can be divided into 1 + 2 + 4, so here s=7,6,4,0
k *= 2; //The number in the group increases because it is an exponential growth of 2 k: 1 2 4 8 (it will jump out directly if it does not reach 8). When k=4, s=4. After this time, it will jump out of the loop directly.
}
//The remaining group
if(s>0)//If s has not reached 0 at this time, it means there is another number c (c in the first picture)
{
cnt + + ;
v[cnt] = a*s; //Volume of the item * Remaining quantity of the item
w[cnt] = b*s;//The value of the item * the remaining quantity of the item
}
}
n = cnt; //The number of enumerations has officially changed from a number to a number of groups. It only needs to be accessed n times in total. For example, 7 only needs to be accessed 3 times.
//01 One-dimensional optimization of backpack
for(int i = 1; i <= n; i + + ) //i is the current item, there are n items in total
for(int j = m; j >=v[i]; j--)//j is the current remaining volume, which must be larger than the size of the item to be operated. The current remaining volume starts from m, and is -1 each time
{
//The current capacity cannot hold the i-th item, then the value of the current volume is equal to the first i-1 items, and the loop will not be entered.
// It can be installed, but it needs to be judged whether to select the i-th item
//Judgment method: The value saved by the capacity of j after traversing to the first i-1 items is compared to the value of the capacity of j-v[i] after traversing to the first i-1 items plus the value of i
//Note that it is traversing to i-1 items, because they may not fit in, so the capacity of j-v[i] is not necessarily the value of i-1
//Why does enumerating backpack capacity need to be in reverse order in one dimension?
//In the two-dimensional case, the state f[i][j] is obtained from the state of the previous round i - 1, and f[i][j] and f[i - 1][j] are independent .
//After optimizing to one dimension, if we are still in positive order, then f [smaller volume] is updated to f [larger volume], then it is possible that the state of the i-1th round should be used but the state of the i-1th round is used. The status of the i wheel.
//For example, if the i-th round of the one-dimensional state makes a decision on an item with a volume of 3, then f[7] is updated from f[4], and the correct f[4] here should be f[i - 1][4 ], but f[4] here in enumeration j from small to large becomes f[i][4] in the i-th round of calculation.
//When enumerating backpack capacity j in reverse order, we find that f[7] is also updated by f[4], but because it is in reverse order, f[4] has not been updated from f[7] to f[4]. f[4] has not been calculated in the i-th round, so the actual calculated f[4] at this time is still f[i - 1][4].
//At this time, w stores the value of the group, not the value of an item.
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
printf("%d\
",f[m]);
return 0;
}
Group backpack problem:
Each group has items of different sizes and values, and only one item can be selected from each group
#include<iostream>
using namespace std;
const int N=110;
int f[N];// f[j], the maximum value of the first i items in j volume
int v[N][N]; // volume
int w[N][N]; // value
int s[N]; //Items in group i
int n,m,k;
int main()
{
scanf("%d%d", & amp;n, & amp;m); //Number of items, backpack capacity
for(int i=1;i<=n;i + + )
{
scanf("%d", & amp;s[i]);//group i
for(int j=1;j<=s[i];j + + )
{
scanf("%d%d", & amp;v[i][j], & amp;w[i][j]);//The volume and value of j item in group i
}
}
for(int i=1;i<=n;i + + )
{
for(int j=m;j>=0;j--)//Let the volume be m from the beginning, and let the volume decrease by 1 each time
{
for(int k=1;k<=s[i];k + + )//Traverse the items in the group
{
if(j>=v[i][k])//If the remaining volume is greater than the volume of the item, determine whether to add the ik item
//Don't want ik items or want ik items, but if you want ik items, look at the capacity - the volume of ik, and how much value is contained in the remaining capacity. Compare again whether you want ik
f[j]=max(f[j],f[j-v[i][k]] + w[i][k]);
}
}
}
printf("%d\
",f[m]);
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57182 people are learning the system