Dynamic programming [1] (knapsack problem)

0/1 knapsack

You can take up to one item per item

 

Practice hand exercises ：2. 01 knapsack problem - AcWing Question bank

Code ：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1010;

ll n,m,v[maxn],w[maxn];

ll ans[maxn][maxn];

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++){

            ans[i][j]=ans[i-1][j];// It doesn't include i About items （ On the left ）

            // Including i In the case of items, it is necessary to judge whether the backpack capacity is greater than No i The volume of items 

            if(j>=v[i]) ans[i][j]=max(ans[i][j],ans[i-1][j-v[i]]+w[i]);

        }

    }

    cout<<ans[n][m]<<endl;

    return 0;

}

One dimensional optimization can be realized here ：

Ideas as follows

Put the two-dimensional i If you delete it all, you can see , It doesn't contain i The situation of ,ans[j]=ans[j] Hang up ; contain i The situation of , because j It's from 0 Traversing m Of , So the conditions j>=v[i] stay 0—v[i] Permanent failure , You can change the start of the loop to j=v[i];j<=m;j++, That is, delete the two-dimensional i For after ans= max(ans[j],ans[j-v[i]]+w[i]), because j-v[i]<j, and j It is traversed from small to large , namely ans(j-v[i]) stay f(j) It has already been calculated by , There are repeated operations and the above ans[j] It's not practical , So we just need to put j Traversal from large to small will not cause the above problems , The correct state transition equation is ans[j]=max(ans[j],ans[j-v[i]]+w[i])

The code is as follows ：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1010;

ll n,m,v[maxn],w[maxn];

ll ans[maxn];

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--){

            // It doesn't include i Items 

            //ans[j]=ans[j];

            // Hang up 



            // Including i Items 

            ans[j]=max(ans[j],ans[j-v[i]]+w[i]);

        }

    }

    cout<<ans[m]<<endl;

    return 0;

}

Completely backpack

Each item has countless

 

Practice hand exercises ：3. Complete knapsack problem - AcWing Question bank

Code （ Not optimized will time out ）：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1010;

ll n,m,v[maxn],w[maxn];

ll ans[maxn][maxn];

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++)

                ans[i][j]=max(ans[i][j],ans[i-1][j-k*v[i]]+w[i]*k);

    cout<<ans[n][m]<<endl;

    return 0;

}

The optimization ideas are as follows ：

The equation of state transfer is ：ans[i][j]=max(ans[i][j],ans[i-1][j-k*v[i]]+w[i]*k)

namely ans[i][j]=max(ans[i-1][j],ans[i-1][j-v]+w,ans[i-1][j-2v]+2w,ans[i-1][j-3v]+3w,....)

ans[i][j-v]=max(          ans[i-1][j-v],   ans[i-1][j-2v]+w, ans[i-1][j-2v]+2w,....)

therefore ans[i][j]=max(ans[i][j-v[i]]+w,ans[i][j])

The code is as follows ：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1010;

ll n,m,v[maxn],w[maxn];

ll ans[maxn][maxn];

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++)

        {

            ans[i][j]=ans[i-1][j];

            if(j>=v[i])

            ans[i][j]=max(ans[i][j],ans[i][j-v[i]]+w[i]);

        }

    cout<<ans[n][m]<<endl;

    return 0;

}

Here we can still optimize from two dimensions to one dimension ：

Ideas as follows

Put the two-dimensional i If you delete it all, you can see , It doesn't contain i The situation of ,ans[j]=ans[j] Hang up ; contain i The situation of , because j It's from 0 Traversing m Of , So the conditions j>=v[i] stay 0—v[i] Permanent failure , You can change the start of the loop to j=v[i];j<=m;j++, That is, delete the two-dimensional i For after ans= max(ans[j],ans[j-v[i]]+w[i]), because j-v[i]<j, and j It is traversed from small to large , namely ans(j-v[i]) stay f(j) It has already been calculated by , In line with reality , The correct state transition equation is ans[j]=max(ans[j],ans[j-v[i]]+w[i])

Code ：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1010;

ll n,m,v[maxn],w[maxn];

ll ans[maxn];

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++)

        {

            ans[j]=max(ans[j],ans[j-v[i]]+w[i]);

        }

    cout<<ans[m]<<endl;

    return 0;

}

Multiple backpack

Each item has a maximum of s[i] individual

 

Practice hand exercises ：4. Multiple knapsack problem I - AcWing Question bank

Code （ The data range is very small. Violence can pass ~）：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1010;

int n,m,v[maxn],w[maxn],s[maxn];

int ans[maxn][maxn];

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]&&v[i]*k<=j;k++)

// Only the judgment condition is one step more than the complete knapsack , Others are exactly the same as full backpack violence 

                ans[i][j]=max(ans[i][j],ans[i-1][j-k*v[i]]+w[i]*k);

    cout<<ans[n][m]<<endl;

    return 0;

}

Practice hand exercises ：5. Multiple knapsack problem II - AcWing Question bank

Using the above violence will time out , The data range here has become larger , The time complexity of violence is 1e9, So here we need to optimize the code , It can be seen that in any case, there is a double cycle , We can optimize the traversal s[i] The cycle of , Go through it alone s[i] want 1e3, We can express it in binary s[i] Make his complexity become logs Level .

for example s=200 when , We can 1,2,4,8,16,32,64,73 namely 2^7-1+73=200. Calculate at least how many items are needed for the third layer of each item , To update each item （ So many ） The occupied volume and value of 01 Template writing of backpack .

The code is as follows ：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=25000,M=2010;

int n,m,v[N],w[N];

int ans[N];

int main(){

    cin>>n>>m;

    int cnt=0;

    for(int i=1;i<=n;i++){

        int a,b,s;

        cin>>a>>b>>s;

        int k=1;

        while(k<=s) {

            cnt++;

            v[cnt]=a*k;

            w[cnt]=b*k;

            s-=k;

            k*=2;

        }

        if(s>0) {

            cnt++;

            v[cnt]=a*s;

            w[cnt]=b*s;

        }

    }

n=cnt;

// use cnt A new item to represent this item , after cnt Express i,m Or backpack volume , To use 01 Backpack to judge whether to choose or not to find the maximum value 

    for(int i=1;i<=n;i++)

        for(int j=m;j>=v[i];j--)

            ans[j]=max(ans[j],ans[j-v[i]]+w[i]);

    cout<<ans[m]<<endl;

    return 0;

}

Pack in groups

Yes n Group items , There are several items in each group , Only one item in the same group can be selected

Practice hand exercises ：9. Group knapsack problem - AcWing Question bank

The code is as follows ：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1000;

int n,m,v[N][N],w[N][N],s[N];

int ans[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--)// When you use the upper layer, you will traverse from large to small 

            for(int k=0;k<s[i];k++)

                if(v[i][k]<=j)

                    ans[j]=max(ans[j],ans[j-v[i][k]]+w[i][k]);

    cout<<ans[m]<<endl;

    return 0;

}