1.01 Backpack Problem
There are N items and a V-pack. The cost of putting item I is c[i], and the value is w[i]. Seek which items to put in your backpack to maximize the total value.
The two-dimensional dynamic equation for the 01 knapsack problem is given directly:
f[i][j]=max(f[i-1][j],f[j-c[i]]+w[i]);
How do you understand that?
Imagine a two-dimensional array f[0...N][0...V], where f[i][j] represents the most valuable option in which the first I items are loaded with a backload of J. Then the whole problem can be planned into many sub-problems, just to grasp the key:
1. If the first item cannot be loaded (i.e. the capacity of the second item exceeds the backpack volume), then f[i][j]=f[i-1][j], which is equivalent to the value of the first I-1 item loaded with the backpack volume of j;
2. If the second item can be loaded, the problem can be converted to the maximum value of the remaining j-c[i] after the second item has been loaded, that is, f[i][j]=f[i-1][j-c[i]+w[i].
From the above description, we can know that f[i][j] needs to be introduced with the aid of the first i-1 items to load a backpack with a capacity of J or the maximum value of a backpack with a capacity of j-c[i]. So the loop code for solving the whole f[0...N][0...V] should be as follows:
for(int i=1;i<=N;i++) for(int j=0;j<=V;j++) f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
Time complexity is O(N*V).
How to optimize? Optimizing time directly for this two-dimensional array is not possible, but we can optimize space. The optimization code is as follows:
for(int i=1;i<=N;i++) for(int j=V;j>=0;j--) f[j]=max(f[j],f[j-c[i]]+w[i]);
In this way, a two-dimensional array becomes a one-dimensional array, which enables space optimization.
How does that work?
In fact, when solving each f[i][j] in two dimensions, utilizing the maximum value of the first i-1 items loaded into the backpack, you can either use a one-dimensional array directly to achieve coverage, either an unchanged f[j], or f[j-c[i]+w[i].
Looking at the second for loop above, j is enumerated in reverse order from V...0. What is the meaning of this?
In fact, when solving f[j], which is equivalent to f[i][j] in two dimensions, we need to know that f[i-1][j] and f[i-1][j-c[i]] are two states. The key to using one-dimensional arrays is to "cover". Each time f[j] whose main loop is i, it must cover f[j] when the main loop is i-1.
But only i f you use reverse order, f[j-c[i]] is the most valuable first i-1 item in your backpack, so you can be confident about covering it with f[j]. Otherwise, when the main loop goes to i, f[j-c[i]] is already f[i][j-c[i], which does not fit the title.
For a simple optimization, the code is as follows (note the comparison):
for(int i=1;i<=N;i++) for(int j=V;j>=c[i];j--) f[j]=max(f[j],f[j-c[i]]+w[i]);
Once you understand the idea of cover above, you can clearly understand this optimization: since item I costs more than the backpack amount j, in fact, f[j]=max(f[j],f[j-c[i]]+w[i]) must result in f[j], that is, the maximum value of a backpack with a capacity of J for the first i-1 items without having to cover.
Example
There are N items and a backpack with a capacity of V. Each item can only be used once. Item i has a volume of vi and a value of wi. Solve which items are loaded into a backpack so that the total volume of these items does not exceed the backpack volume and the total value is greatest. Output maximum value.
Input Format
The first two integers, N and V, are separated by spaces to indicate the number of items and the backpack area.
Next, there are N lines, two integers vi,wi in each line, separated by spaces, representing the volume and value of item i I.
Output Format
Output an integer representing the maximum value.
Data Range
0<N,V≤1000
0<vi,wi≤1000
sample input
4 5
1 2
2 4
3 4
4 5
Output sample:
8
The code is as follows:
#include<bits/stdc++.h>
using namespace std;
int f[1005];
int main(){
int n,v;
scanf("%d%d",&n,&v);
int *c=new int[n+1];
int *w=new int[n+1];
for(int i=1;i<=n;i++)scanf("%d%d",&c[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=v;j>=c[i];j--)
f[j]=max(f[j],f[j-c[i]]+w[i]);
printf("%d\n",f[v]);
}
The key is that the title requires only one item per item and cannot be repeated. Keep this in mind, and then compare it to the full backpack problem.
2. Full Backpack Problem
There are N items and a V-sized backpack, each of which has unlimited items available. The cost of item I is c[i]c[i], and the value is w[i]w[i]. Solving which items to load into a backpack will allow the total cost of these items to not exceed the amount of backpack and will maximize the total value.
The difference between the full backpack problem and the 01 backpack problem is that every item has an unlimited number of items available. So for each item, K can be selected, where k satisfies k*c[i]<=j, then the two-dimensional state transfer equation is:
f[i][j]=max(f[i-1][j],f[i-1][j-kc[i]]+kw[i]);(k*c[i]<=j)
The simplest code can be written as follows:
for(int i=1;i<=N;i++) for(int j=0;j<=V;j++) for(int k=1;k*c[i]<=j;k++) f[i][j]=max(f[i-1][j],f[i-1][j-k*c[i]]+k*w[i]);
f[i][j] indicates the maximum value of a bag with a capacity of J for the first item. Note that the first item is not the first one and that the same item can be selected multiple times.
Optimize Idea: Turn the full backpack problem into a solution to the 01 backpack problem. For each item i, choose at most V/c[i], and then convert it into V/c[i] items of the same cost and value. The code is as follows:
for(int i=1;i<=N;i++) for(int j=c[i];j<=V;j++) f[j]=max(f[j],f[j-c[i]]+w[i]);
Note the difference between this and the 01 backpack: the second layer of the loop here is sequential, because each item can be selected repeatedly, so for each item i (main loop), you can ask, cover, and the equation of state can actually be understood as:
f[i][j]=max(f[i-1][j],f[i][j-c[i]]+w[i])
If it is a two-dimensional array, in fact, it does not matter if the second-level loop order is in reverse order, as long as the equation of state is satisfied, but in order to optimize space, using one-dimensional arrays to achieve multiple override operations, we need to understand the problem of mastering the second-level loop order.
This optimization idea can expand more:
The cost of splitting the second item into several pieces is c[i] × 2^k, value w[i] × Several items of 2^k, where k satisfies c[i] × 2^k<=V
This takes advantage of the idea of binary because, in fact, no matter how many i-items you choose, you can think of them as the sum of several binary numbers (if you choose five i-items, you can choose one c[i] × 2^0 and c[i] × 2^2). This makes the items different and the problem turns into a 01 backpack problem.
Example
There are N items and a backpack with a capacity of V. Each item has unlimited items available. The volume of item i I is vi and the value is wi. Solve which items are loaded into a backpack so that the total volume of these items does not exceed the backpack volume and the total value is greatest. Output maximum value.
Input Format
The first row contains two integers, N and V, separated by spaces, representing the number of items and the backing area, respectively. Next, there are N lines, two integers vi,wi in each line, separated by spaces, representing the volume and value of item i I.
Output Format
Output an integer representing the maximum value.
Data Range
0<N,V≤1000
0<vi,wi≤1000
sample input
4 5
1 2
2 4
3 4
4 5
Output sample:
10
The code is as follows:
#include<bits/stdc++.h>
using namespace std;
int f[1005];
int main(){
int n,v;
scanf("%d%d",&n,&v);
int *c=new int[n+1];
int *w=new int[n+1];
for(int i=1;i<=n;i++)scanf("%d%d",&c[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=c[i];j<=v;j++)
f[j]=max(f[j],f[j-c[i]]+w[i]);
printf("%d\n",f[v]);
}
3. Multiple Backpack Problem
There are N items and a V-pack. The maximum number of p[i] items available for item I is c[i] per item at a cost of w[i]. Solving which items to load into a backpack will allow the total cost of these items to not exceed the amount of backpack and will maximize the total value.
This problem is similar to a full backpack problem where each item can be selected indefinitely and only k*c[i]<=V is required. In contrast, the multiple backpack problem adds a restriction to the full backpack, that is, k<=p[i]. The simplest one-dimensional code is easy to write:
for(int i=1;i<=N;i++) for(int j=V;j>=c[i];j--) for(int k=1;k<=p[i]&&k*c[i]<=j;k++) f[j]=max(f[j],f[j-k*c[i]]+k*w[i]);
Optimize: Take advantage of the previous extended optimization for the full backpack problem, that is, use the binary concept, but must meet the restriction that the number of items I can not exceed p[i]. The code is as follows:
for(int i=1;i<=N;i++){
int num=min(p[i],V/c[i]);
for(int k=1;num>0;k<<=1){
if(k>num)k=num;
num-=k;
for(int j=V;j>=k*c[i];j--)
f[j]=max(f[j],f[j-k*c[i]]+k*w[i]);
}
}
Example
There are N items and a backpack with a capacity of V. Item i has a maximum of si s, with a volume of vi and a value of wi. Solve which items are loaded into the backpack so that the total volume of the items does not exceed the backpack volume and the total value is maximum. Output maximum value.
Input Format
The first row contains two integers, N and V, separated by spaces, representing the number of items and the backing area, respectively. Next, there are N lines, each with three integers vi,wi,si, separated by spaces, representing the volume, value, and quantity of item i I.
Output Format
Output an integer representing the maximum value.
Data Range
0<N,V≤100
0<vi,wi,si≤100
sample input
4 5
1 2 3
2 4 1
3 4 3
4 5 2
Output sample:
10
The code is as follows:
#include<bits/stdc++.h>
using namespace std;
int f[1005];
int main(){
int N,V;
scanf("%d%d",&N,&V);
int *c=new int[N+1];
int *w=new int[N+1];
int *s=new int[N+1];
for(int i=1;i<=N;i++)scanf("%d%d%d",&c[i],&w[i],&s[i]);
for(int i=1;i<=N;i++){
int num=min(s[i],V/c[i]);
for(int k=1;num>0;k<<=1){
if(k>num)k=num;
num-=k;
for(int j=V;j>=k*c[i];j--)
f[j]=max(f[j],f[j-k*c[i]]+k*w[i]);
}
}
printf("%d\n",f[V]);
}
Optimizing the algorithm with binary thinking is already the best way for chickens to master. What's more, using monotonic queues to master and share over time.
4. Mixed Backpack Problem
Mix the first three backpack problems together
Just distinguish the order clearly and in reverse order, and give the code directly (p[i] 0 means that the item can only be taken once, and -1 means that the item can be taken countless times, otherwise it can take up to p[i] item i):
for(int i=1;i<=N;i++){
if(p[i]==0)//01 Backpack
for(int j=V;j>=c[i];j--)
f[j]=max(f[j],f[j-c[i]]+w[i]);
else if(p[i]==-1)//Full Backpack
for(int j=c[i];j<=V;j++)
f[j]=max(f[j],f[j-c[i]]+w[i]);
else{//MultiplePack
int num=min(p[i],V/c[i]);
for(int k=1;num>0;k<<=1){
if(k>num)k=num;
num-=k;
for(int j=V;j>=k*c[i];j--)
f[j]=max(f[j],f[j-k*c[i]]+k*w[i]);
}
}
}
Example
There are N items and a backpack with a capacity of V.
There are three types of items:
Category 1 items can only be used once (01 backpack);
The second kind of items can be used indefinitely (full backpack);
Class III items can only be used up to si times (multiple backpacks);
Each volume is vi and the value is wi.
Solve which items are loaded into the backpack so that the total volume of the items does not exceed the backpack volume and the total value is maximum. Output maximum value.
Input Format
The first row contains two integers, N and V, separated by spaces, representing the number of items and the backing area, respectively. Next, there are N lines, each with three integers vi,wi,si, separated by spaces, representing the volume, value, and quantity of item i I.
si=1 means item i can only be used once;
si=0 means that item i can be used indefinitely;
si>0 means that the second item can be used si times;
Output Format
Output an integer representing the maximum value.
Data Range
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000
sample input
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
Output sample:
8
The code is as follows:
#include<bits/stdc++.h>
using namespace std;
int f[1005];
int main(){
int n,v,c,w,s;
scanf("%d%d",&n,&v);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&c,&w,&s);
if(s==-1)
for(int j=v;j>=c;j--)
f[j]=max(f[j],f[j-c]+w);
else if(s==0)
for(int j=c;j<=v;j++)
f[j]=max(f[j],f[j-c]+w);
else{
int num=min(s,v/c);
for(int k=1;num>0;k<<=1){
if(k>num)k=num;
num-=k;
for(int j=v;j>=k*c;j--)
f[j]=max(f[j],f[j-k*c]+k*w);
}
}
}
printf("%d\n",f[v]);
}
5. Two-dimensional Expense Backpack Problem
There are two different fees for each item; Both costs must be paid for choosing this item; For each cost, there is a maximum value that can be paid (backload). Ask how you can choose your items to get the most value. The two costs for setting item I are c[i] and g[i], respectively. The maximum value that can be paid for both costs (the two backpacks) is V and M, respectively. The value of the item is w[i].
Here the equation of state needs to be added one more dimension, and the three-dimensional equation of state is:
f[i][j][k]=max(f[i-1][j][k],f[i-1][j-c[i]][k-g[i]]+w[i])
Where f[i][j][k] represents the maximum value of the first two items at two maximum costs of J and k, respectively.
Based on the above ideas about overrides, the solution code can be written as follows:
for(int i=1;i<=N;i++) for(int j=V;j>=c[i];j--) for(int k=M;k>=g[i];k--) f[j][k]=max(f[j][k],f[j-c[i]][k-g[i]]+w[i]);
This type of title may be given implicitly, for example, with a restriction on a general 01 backpack problem: if the number of items selected is not greater than M, it can actually be understood that each item has g[i], in addition to the cost c[i], and g[i] is 1. If another backpack with a capacity of M is loaded, add a third layer of loop directly:
for(int K=M;k>=1;k–)
f[j][k] then represents the maximum value at which the cost J is paid and no more than k items are selected.
Example
There are N items and a backpack with a capacity of V. The maximum weight the backpack can bear is M. Each item can only be used once. Volume is vi, weight is mi, value is wi. Solve which items to load into a backpack so that the total size of the items does not exceed the backpack volume, the total weight does not exceed the maximum weight that the backpack can bear, and the total value is the maximum. Output maximum value.
Input Format
The first row contains three integers, N,V,M, separated by spaces, representing the number of items, the backpack volume, and the maximum weight that a backpack can bear. Next, there are N lines, each with three integers vi,mi,wi, separated by spaces, representing the volume, weight, and value of item i I.
Output Format
Output an integer representing the maximum value.
Data Range
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
sample input
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
Output sample:
8
The code is as follows:
#include<bits/stdc++.h>
using namespace std;
int f[105][105];
int main(){
int N,V,M,v,m,w;
scanf("%d%d%d",&N,&V,&M);
for(int i=1;i<=N;i++){
scanf("%d%d%d",&v,&m,&w);
for(int j=V;j>=v;j--)
for(int k=M;k>=m;k--)
f[j][k]=max(f[j][k],f[j-v][k-m]+w);
}
printf("%d\n",f[V][M]);
}
6. Group Backpack Problem
There are N items and a V-pack. The cost of item I is c[i], and the value is w[i]. These items are divided into groups, each of which conflicts with each other, with a maximum of one selected item. Solving which items to load into a backpack will allow the total cost of these items to not exceed the amount of backpack and will maximize the total value.
Compare directly with 01 backpack, the key to 01 backpack handling is to solve each f[i][j] in two situations, the first item being put in and not put in. The two cases of f[i][j] in a grouped backpack are when either group I is selected or not, then the equation of state is:
f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i])
Form is the same as 01 backpack, but there are differences in understanding. Continue to use a scrolling array (to achieve overrides), and the solution code is as follows (because factors include the number, cost, and value of each group, which is slightly more complex, just use a structure variable, Node):
Structural variable construction code:
typedef struct{
int c[1005];//cost
int v[1005];//value
int s;//Number of items per group
}Node;
Node node[1005];
Solve equation code:
for(int i=1;i<=N;i++){
scanf("%d",&node[i].s);//Number of items in group i
for(int j=1;j<=node[i].s;j++)scanf("%d%d",&node[i].c[j],&node[i].w[j]);
}
for(int i=1;i<=N;i++)//There are N groups
for(int j=V;j>=0;j--)
for(int k=1;k<=node[i].s;k++)
if(j>=node[i].c[k])
f[j]=max(f[j],f[j-node[i].c[k]]+node[i].w[k]);
//Since only one item is taken from each group, the optimal solution achieved by the items in the previous group can be overridden.
In fact, multiple backpacks are a special case of grouping backpacks. Multiple backpacks are just the same items for each group.
Example
There are N items and a backpack with a capacity of V. There are several items in each group, and only one item in the same group can be selected at most. The volume of each item is vij, the value is wij, where i is the group number and j is the group number.
Solve which items are loaded into the backpack so that the total size of the items does not exceed the backpack volume and the total value is greatest.
Output maximum value.
Input Format
The first line has two integers, N and V, separated by spaces, representing the number of item groups and the amount of backpack.
Next, there are N sets of data:
The first row of each set of data has an integer Si, which represents the number of items in the ith item group.
Each set of data is followed by Si lines, each with two integers vij,wij, separated by spaces, representing the volume and value of the jth item in the ith item group.
Output Format
Output an integer representing the maximum value.
Data Range
0<N,V≤100
0<Si≤100
0<vij,wij≤100
sample input
3 5
2
1 2
2 4
1
3 4
1
4 5
Output sample:
8
The code is as follows:
#include<bits/stdc++.h>
using namespace std;
int f[105];
int main(){
int N,V,s;
scanf("%d%d",&N,&V);
for(int i=1;i<=N;i++){
scanf("%d",&s);
int *v=new int[s+1];
int *w=new int[s+1];
for(int j=1;j<=s;j++)scanf("%d%d",&v[j],&w[j]);
for(int j=V;j>=0;j--)//Object is group i
for(int k=1;k<=s;k++)//Notice the order of these two loops
if(j>=v[k])
f[j]=max(f[j],f[j-v[k]]+w[k]);
//Perform an inverse loop of back containment before iterating the number of items in group i
//This allows you to select up to one item per group
}
printf("%d\n",f[V]);
}
To better understand and think about rolling arrays!
7. Dependent Backpack Problems
Dependencies exist between items and between i and j. If i is selected, j is required.
Insufficient strength, put on hold for now.
8. Number of solutions for backpack problems
In fact, it's still the idea of state transition. Take 01 backpack as an example, cnt array is used to represent the number of scenarios, f array is used to represent the maximum value,
f[j] denotes the maximum value when the backpack is j, and cnt[j] denotes the number of scenarios where the backpack is j to maximize the value
In the main cycle, if the total value increases after the second item is added, then it must be added. At this time, cnt[j]=cnt[j-v], which is equal to the maximum value of J-V backpack. Adding item i on this basis does not affect the number of programs. If the total value is unchanged, then cnt[j]+=cnt[j-v], which is equivalent to the scheme of maximizing the total value of J capacity, is directly added to the scheme of maximizing the total value of J-V capacity. The code is as follows:
for(int i=1;i<=N;i++)
for(int j=V;j>=c[i];j--){
int value=f[j-c[i]]+w[i];
if(value>f[j])
f[j]=value,cnt[j]=cnt[j-c[i]];
else if(value==f[j])
cnt[j]+=cnt[j-c[i]];
}
It is important to note that the initial cnt value is 1, because a value of 0 is also a solution when nothing is installed.
Example
There are N items and a backpack with a capacity of V. Each item can only be used once. Item i has a volume of vi and a value of wi. Solve which items are loaded into a backpack so that the total volume of these items does not exceed the backpack volume and the total value is greatest. The number of scenarios that output the optimal selection. Note that the answer may be large, please output the result of answer mode 109+7.
Input Format
The first two integers, N and V, are separated by spaces to indicate the number of items and the backpack area. Next, there are N lines, two integers vi,wi in each line, separated by spaces, representing the volume and value of item i I.
Output Format
Output an integer representing the result of the scheme modulus 109+7.
Data Range
0<N,V≤1000
0<vi,wi≤1000
sample input
4 5
1 2
2 4
3 4
4 6
Output sample:
2
The code is as follows:
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
const int mod=1e9+7;
int f[1050],cnt[1050];
int main(){
int N,V,v,w;
scanf("%d%d",&N,&V);
for(int i=0;i<=V;i++)cnt[i]=1;
for(int i=1;i<=N;i++){
scanf("%d%d",&v,&w);
for(int j=V;j>=v;j--){
int value=f[j-v]+w;
if(value>f[j])
f[j]=value,cnt[j]=cnt[j-v];
else if(value==f[j])
cnt[j]=(cnt[j]+cnt[j-v])%mod;
}
}
printf("%d\n",cnt[V]);
}
Finally, I would like to give you another topic on a board recently brushed by HNUCM:
Digging Gems
Title Description
Kimi designed a game to dig gems. There are many different types of gems in the game, such as rubies, sapphires, emeralds and of course expensive diamonds.
Now give a map with N different gems on it. Each gem has one or more gems, and each gem of the same kind has the same value.
In addition, each gem has a mining time.
The winner of the game is the player who digs the most valuable gems in a given time.
Now the number of different gems in class N, the value of each gem in each class, and the mining time are given, and a total game time T is given. What is the maximum value you can get, regardless of your competitors?
input
Single set of inputs.
Line 1 enters a positive integer N and a positive integer T, representing the number of gem types and the total game time (minutes), separated by spaces. N<=100, T<=1000.
Three positive integers, X[i], Y[i], and Z[i], from line 2 to line N+1, represent the number of gems in class i, the value of a gem in class i, and the mining time (minutes), respectively. X[i], Y[i] and Z[i] do not exceed 100.
output
The maximum value that the output can achieve.
sample input
3 10
2 5 5
3 4 3
2 8 6
sample output
12
The code is as follows:
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
int f[1050];
int main(){
int N,T,x,y,z;
scanf("%d%d",&N,&T);
for(int i=1;i<=N;i++){
scanf("%d%d%d",&x,&y,&z);
int num=min(x,T/z);
for(int k=1;num>0;k<<=1){
if(k>num)k=num;
num-=k;
for(int j=T;j>=k*z;j--)
f[j]=max(f[j],f[j-k*z]+k*y);
}
}
printf("%d\n",f[T]);
}