Mainly write: 0-1 backpack, complete backpack (unlimited number of coins in change), multiple backpack (limited number of coins in change), fractional backpack

0-1 backpack: there are N items and a backpack with a capacity of V. each item can only be used once. The volume of article I is v[i], and the value is w[i]. Solve which items are loaded into the backpack, so that the total volume of these items does not exceed the backpack capacity, and the total value is the largest.

Complete backpack: there are N items and a backpack with a capacity of V. there are unlimited items available for each item. The volume of article I is v[i], and the value is w[i]. Solve which items are loaded into the backpack, so that the total volume of these items does not exceed the backpack capacity, and the total value is the largest.

Multiple backpacks: there are N items and a backpack with a capacity of V. There are at most n[i] items available for item I. each item has a volume of v[i] and a value of w[i]. Solve which items are loaded into the backpack, so that the total volume of these items does not exceed the backpack capacity, and the total value is the largest.

Fractional knapsack: there are n items. The weight and value of the ith item are w[i] and v[i] respectively. The capacity of the backpack is V. how to make the items loaded in the backpack have a greater total value (a part of the items can be taken)

difference:
You will find that the difference lies in the number of each kind of backpack. 01 backpack is only one piece of each kind, complete backpack is infinite pieces of each kind, and multiple backpacks are limited pieces of each kind. These three are written using the method of dynamic programming.

The difference between fractional knapsack and 01 knapsack is that if an item cannot be put in all, it can be put in part, and greedy thinking is adopted.

I 0-1 Backpack

2D array code:

#include<bits/stdc++.h>
using namespace std;
int n,V,v[105],w[105],dp[105][1005];//dp[i][j] represents the maximum value stored when the capacity is j after I items are loaded
int main()
{
    cin>>n>>V;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=V;j++)
        {
            if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n][V];
}

Space optimization is used to optimize into a one-dimensional array:
Note that the cycle of j must start in reverse order from large to small

#include<bits/stdc++.h>
using namespace std;
int n,V,v[105],w[105],dp[1005];//dp[j] the maximum value stored when the capacity is j
int main()
{
    cin>>n>>V;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>0;j--)
        {
            if(j>=v[i]) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[V];
}

2, Complete Backpack

1. Complete knapsack problem

2D array code:
Unlike the 0-1 knapsack, the state transition equation

if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);//Different from 0-1 Backpack

#include<bits/stdc++.h>
using namespace std;
int n,V,v[105],w[105],dp[105][1005];//dp[i][j] represents the maximum value stored when the capacity is j after I items are loaded
int main()
{
    cin>>n>>V;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=V;j++)
        {
            if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);//Different from 0-1 Backpack
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n][V];
}

Space optimized one-dimensional array:
Different from the 0-1 knapsack, note that the cycle of j is in positive order

#include<bits/stdc++.h>
using namespace std;
int n,V,v[105],w[105],dp[1005];//dp[j] the maximum value stored when the capacity is j
int main()
{
    cin>>n>>V;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=V;j++)
        {
            if(j>=v[i]) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[V];
}

2. Similar coins have unlimited change

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n=0,c[1005],k,x,dp[1005];//dp[i] means the minimum number of coins used for I
    cin>>k;
    while(cin>>x)
    {
        c[n++]=x;
    }
    for(int i=0;i<=k;i++)
    {
        if(i==0) dp[i]=0;
        else dp[i]=999999999;
    }
    for(int i=0;i<n;i++)
    {
        dp[c[i]]=1;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=c[i];j<=k;j++)
        {
            dp[j]=min(dp[j],dp[j-c[i]]+1);
        }
    }
    cout<<dp[k];
}

3, Multiple Backpack

1. Multiple knapsack problem
Just add an additional cycle and disassemble n identical items, which is the 0-1 knapsack problem

2D array:

#include<bits/stdc++.h>
using namespace std;
int N,V,v[105],w[105],n[105],dp[105][1005];//dp[i][j] represents the maximum value stored when the capacity is j after I items are loaded
int main()
{
    cin>>N>>V;
    for(int i=1;i<=N;i++)
    {
        cin>>v[i]>>w[i]>>n[i];
    }
    for(int i=1;i<=N;i++)
    {
        for(int k=1;k<=n[i];k++)
        {
            for(int j=1;j<=V;j++)
            {
                if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
                else dp[i][j]=dp[i-1][j];
            }
        }
        
    }
    cout<<dp[n][V];
}

One dimensional array optimization:

#include<bits/stdc++.h>
using namespace std;
int N,V,v[105],w[105],n[105],dp[1005];//dp[j] the maximum value stored when the capacity is j
int main()
{
    cin>>N>>V;
    for(int i=1;i<=N;i++)
    {
        cin>>v[i]>>w[i]>>n[i];
    }
    for(int i=1;i<=N;i++)
    {
        for(int k=1;k<=n[i];k++)
        {
            for(int j=1;j<=V;j++)
            {
                if(j>=v[i]) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
        }

    }
    cout<<dp[V];
}

2. There is a limit on the number of change coins for similar coins

Compared with the unlimited problem, there is an additional layer of circulation to judge the number of coins

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t[11],coins[11],dp[20002];
    int n,m;
    cin>>n;
    for(int i=0;i<n;i++)
    {
            cin>>t[i]>>coins[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++)
        dp[i]=9999;
    for(int i=0;i<n;i++)
    {
        for(int j=1;j<=coins[i];j++)
        {
            for(int k=t[i];k<=m;k++)
                dp[k]=min(dp[k],dp[k-t[i]]+1);
        }
    }
    cout<<dp[m];
}

4, Fractional knapsack

Idea: divide the value of the item by its capacity to find the value p of the unit capacity, and then use the greedy idea to load the large P first.

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int w,v;
    double p;
}a[1005];

int cmp(node a,node b)
{
    return a.p>b.p;
}

int main()
{
    int n,c;
    double ans=0;
    cin>>n>>c;
    if(n==0 || c==0) return 0;
    for(int i=0;i<n;i++)
        cin>>a[i].v;
    for(int i=0;i<n;i++)
        cin>>a[i].w;
    for(int i=0;i<n;i++)
        a[i].p=(double)a[i].v/a[i].w;
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++)
    {
        if(a[i].w<=c)
        {
            ans+=a[i].v;
            c-=a[i].w;
        }
        else
        {
            ans+=a[i].p*c;
            break;
        }
    }
    cout<<ans;

}