The knapsack problem refers to the problem of how to obtain the highest value under given conditions
01Backpack problem
Given a weight limit, and the values and weights of several different items, only one of each item, find what is the maximum value that can be obtained
01 The knapsack problem basically refers to the fact that there is only one of the same kind of items. How to obtain the maximum benefit under given constraints?
Enumeration: find all combinations
Dynamic programming
The key to the problem is whether we want to select the current item and whether the current item is the greatest value.
Make an n^2 algorithm
The inner loop represents finding the appropriate size
The outer loop indicates which item
Each time through the inner loop, the first thing we look for is whether we can drop the current item.
After putting down the current item, whether it is worth more than the previous item, choose the higher value.
Then continue to check whether the remaining space can hold the previous items, and if so, compare it with the result of the previous round, whichever is higher.
Since the highest value is taken in each round, there is no need to discuss other items before the previous round. The question only asks for the final value.
The inner loop always finds the current value plus the previous highest value. The previous value has nothing to do with the current item, so it will naturally not be selected repeatedly.
#include<iostream>
using namespace std;
const int maxn = 1000;
int dp[20][20];
int value[20],weight[20]; int main(){ int n,limitw; cin>>n>>limitw; //Number of items, backpack size for (int i=1;i<=n;i++){ cin>>value[i]>>weight[i]; } cout<<"0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20\n"; //Better observation algorithm for(int i=1;i<=n;i++){ for(int j=0;j<=limitw;j++){ /*The only point of the algorithm*/ if(j>=weight[i]){ dp[i][j]=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j]); }else{ dp[i][j]=dp[i-1][j]; //If you can't let it go, inherit the results of the previous round. } cout<<dp[i][j]<<" "; //Better observation algorithm } cout<<"\n"; //Better observation algorithm } cout<<dp[n][limitw]; return 0;
}
Optimize space complexity
We found that we only compared the results of the current round and the previous round. The previous space was useless after being used once.
As long as we search backwards, we can find the maximum value without destroying the value of the previous round of low weight.
The space complexity is given by n^2➡n
#include<iostream>
using namespace std;
const int maxn = 1000;
int dp[20];
int value[20],weight[20]; int main(){ int n,limitw; cin>>n>>limitw; for (int i=1;i<=n;i++){ cin>>value[i]>>weight[i]; } cout<<"0 1 2 3 4 5 6 7 8 9 10\n"; //Better observation algorithm for(int i=1;i<=n;i++){ for(int j=limitw;j>=weight[i];j--){ dp[j]=max(dp[j-weight[i]]+value[i],dp[j]); cout<<dp[j]<<" "; //Better observation algorithm } cout<<"\n"; //Better observation algorithm } cout<<dp[limitw]; return 0;
}
02Multiple backpack problems
There are N kinds of items, the volume of the i-th item is Ci, the value is Wi, and the quantity of each item is limited, Ni. The existing backpack with a capacity of V is put into a number of items to make the total value as large as possible under the condition that the total volume does not exceed V.
Without the need to record the types of items, the 01 backpack is a multiple backpack problem in which the number of each item is 1, so the algorithm of the 01 backpack can still be used to split the items into pieces.
#include<iostream>
using namespace std;
int dp[21][1010]; //Item upper limit, backpack size
int w[10],c[21],n[21]; //value, volume, quantity
int main(){ int N,V; cin>>N>>V; for(int i=1;i<=N;i++){ cin>>w[i]>>c[i]>>n[i]; } for(int i=1;i<=N;i++){ //Which item for(int j=0;j<=V;j++){ //Backpack size for(int k=0;k<=n[i];k++){ //Here, the items are actually placed inside one by one. if(j>=c[i]*k){ dp[i][j]=max(dp[i-1][j-c[i]*k]+w[i]*k,dp[i][j]); } } } } cout<<dp[N][V]<<endl; return 0;
}
Space complexity can still be optimized, the same as 01 backpack
#include<iostream>
using namespace std;
int dp[1010]; //Backpack size
int w[10],c[21],n[21]; //value, volume, quantity
int main(){ int N,V; cin>>N>>V; for(int i=1;i<=N;i++){ cin>>w[i]>>c[i]>>n[i]; } for(int i=1;i<=N;i++){ //Which item for(int j=V;j>=0;j--){ //The size of the backpack must be reversed to optimize space complexity. for(int k=0;k<=n[i];k++){ //Here, the items are actually placed inside one by one. if(j>=c[i]*k){ dp[j]=max(dp[j-c[i]*k]+w[i]*k,dp[j]); } } } } cout<<dp[V]<<endl; return 0;
}
test case
5 10 2 1 2 3 5 3 2 5 1 3 4 2 4 3 8 Deserve result: 14
03Complete backpack problem
Unlimit the quantity of each item in the multi-knapsack problem
5 10 2 1 3 5 2 5 3 4 4 3 Deserve result: 20
Solution: Convert to multiple knapsack problems
In fact, it can be solved directly by using multiple backpacks, but the time complexity is close to o(n v v), because although there is no upper limit on the number of items, the upper limit of the number of items is actually the upper limit of the backpack, and only the number of items * volume < remaining space needs to be processed.
After observation, we found that in the previous multi-knapsack problem, the third loop was just to limit the number
The difference from the 01 backpack is that the 01 backpack records the results of the same item in each round, while the complete backpack records the result of storing an item multiple times, which is specifically reflected in the update of dp. In the 01 backpack, when we put down the current item, we take out the previous records from the previous round and store the previous items. However, the complete backpack slows down the current type in each round, and then takes the maximum value that can be obtained each time. I personally think there is a greedy thought in it.
#include<iostream>
using namespace std;
int dp[21][1010]; //Item upper limit, backpack size
int w[10],c[21]; //value,volume
int main(){ int N,V; cin>>N>>V; for(int i=1;i<=N;i++){ cin>>w[i]>>c[i]; } for(int i=1;i<=N;i++){ //Which item for(int j=0;j<=V;j++){ //Backpack size if(j>=c[i]){ dp[i][j]=max(dp[i][j-c[i]]+w[i],dp[i-1][j]); }else{ dp[i][j]=dp[i-1][j]; } } } cout<<dp[N][V]<<endl; return 0;
}
Space complexity can also be optimized
The inner loop of the algorithm after the optimization of the complete knapsack problem is different from the previous one, because the previous loop was reversed to avoid destroying the records of the previous round. However, the complete knapsack problem does not use the records of the previous round.
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
int dp[1010]; //Backpack size
int w[10],c[21]; //value,volume
int main(){ int N,V; cin>>N>>V; for(int i=1;i<=N;i++){ cin>>w[i]>>c[i]; } for(int i=1;i<=N;i++){ //Which item for(int j=1;j<=V;j++){ //Backpack size dp[j]=max(dp[j-c[i]]+w[i],dp[j]); } } cout<<dp[V]<<endl; return 0;
}