Classification of knapsack problems:
1. 01 knapsack problem
2. Complete knapsack problem
3. Multiple knapsack problem
4. Complete knapsack problem
Solutions to DP problems:
- 01 knapsack problem
Problem Description: see example: 01 knapsack problem
Problem analysis: for each item, you can choose to or not. Therefore, the calculation of state is to update the set represented by I. therefore, f(i,j) = max(f[i-1][j], f[i-1][j-v[i]]+w[i]). This is the 01 knapsack problem of the simple version. The code is as follows:
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j = 0;j<=m;j++)
{
f[i][j] = f[i-1][j];//Don't select the i-th item
if(v[i] <= j) f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]); //See if it's better to choose the i-th one
}
}
cout<<f[n][m]<<endl;
return 0;
}
Optimization: we can find that f in I state is only related to i-1, so we can optimize with rolling array, and only one-dimensional array can save the answer. At this time, the j cycle needs to be from m to v[i], because the state of j-v[i] needs to be updated after the j state. The code is as follows:
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j = m;j >= v[i];j--)
{
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
return 0;
}
2. Complete knapsack problem Complete knapsack problem
Problem analysis: for each item, you can choose no or any number of items (the selected volume needs to be less than V)
The plain version code is as follows: (timeout)
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N],w[N];
int n,m;
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k = 0;k*v[i] <= j;k++)
{
f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<<f[n][m]<<"\n";
return 0;
}
The optimization is as follows:
f[i][j] = max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,...f[i-1][j-kv]+k*w)
f[i[j-v] = max( f[i-1][j-v], f[i-1][j-2v]+w,f[i-1][j-3v]+2w,...f[i-1][j-kv]+(k-1)w)
The first one adds a w to the second one.
Therefore, f[i][j] can be optimized to max(f[i][j],f[i][j-v]+w);
The code is as follows:
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N],w[N];
int n,m;
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j] = f[i-1][j];
if(j >= v[i]) f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);
}
}
cout<<f[n][m]<<"\n";
return 0;
}
Finally, according to the above update method, according to the rolling array, it is optimized into one-dimensional.
Because the status update here is based on this layer, there is no need to reverse the order.
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N],w[N];
int n,m;
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=m;j++)
{
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<"\n";
return 0;
}
3. Multiple knapsack problem Multiple backpack I
Problem analysis, the difference is that the number is not unlimited, so it can be modified slightly
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m;
int v[N],w[N],s[N];
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i]>>s[i];
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k = 0;k<=s[i]&&k*v[i]<=j;k++)
{
f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<<f[n][m]<<endl;
return 0;
}
Multiple knapsack optimization Multiple knapsack problem II
Here, binary is used for optimization. Each item can be represented by 1,2,4,8... Binding, so this problem can be transformed into 01 knapsack problem. The item is the item after binding. Write the final code directly here:
#include<bits/stdc++.h>
using namespace std;
const int N = 1010,M = 25000;
int n,m;
int v[M],w[M];
int f[M];
int main()
{
cin>>n>>m;
int cnt = 0;//Calculate bundle number
for(int i = 1;i<=n;i++)
{
int a,b,s;
cin>>a>>b>>s;
int k = 1;
while(k <= s)
{
cnt++;
v[cnt] = k*a;
w[cnt] = k*b;
s -= k;
k*=2;
}
if(s) {cnt++;v[cnt] = s*a,w[cnt] = s*b;}
}
n=cnt;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
return 0;
}
4. Group knapsack problem: Group Backpack
Plain version:
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m;
int v[N][N],w[N][N],s[N];
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
for(int j=0;j<s[i];j++)
{
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j =0;j<=m;j++)
{
f[i][j] = f[i-1][j];
for(int k=0;k<s[i];k++)
{
if(v[i][k] <= j) f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[n][m]<<endl;
return 0;
}
Optimize according to the method just described
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m;
int v[N][N],w[N][N],s[N];
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
for(int j=0;j<s[i];j++)
{
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j =m;j>=0;j--)
{
for(int k=0;k<s[i];k++)
{
if(v[i][k] <= j) f[j] = max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[m]<<endl;
return 0;
}
That's the end of the knapsack problem
Reference: ACWing basic course