[backpack DP] backpack problem

Complete knapsack problem

subject

explain

• Because each item can choose unlimited pieces , So when we decide to use an item , The number of pieces needs to be considered
• So the expression is in the form of the first formula
• 
•   Look at the second expression f[i,j-v] In the form of , There is only one difference from the first w[i]
• Therefore, the recurrence relation can be expressed as
• f(i,j)=max(f(i,j-v)+w,f(i-1,j);

Code segment

#include<iostream>
using namespace std;
const int N=1010;
int f[N][N],v[N],w[N];
int n,m;
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]<<endl;
    
}