背包问题

01背包

#include<bits/stdc++.h>
using namespace std;
int n,m,f[1001],v[1001],w[1001];
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-v[i]]+w[i],f[j]);
    }
    cout<<f[m];
}

完全背包

#include<bits/stdc++.h>
using namespace std;
int n,m,f[1001],v[1001],w[1001];
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-v[i]]+w[i],f[j]);
    }
    cout<<f[m];
}

多重背包（easy

#include<bits/stdc++.h>
using namespace std;
int n,m,f[1001],v[101],w[101],l[101];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i]>>l[i];
    
    for(int i=1;i<=n;i++)
        for (int k = 1; k <= l[i];k++)
            for (int j = m; j >= v[i]; j--)
                f[j] = max(f[j - v[i]] + w[i], f[j]);
    cout<<f[m];
}

多重背包（hard

#include<bits/stdc++.h>
using namespace std;
const int N=2001;
int n, m, f[N], v[N], w[N], l[N];

int qpow(int x,int k)
{
    int ans=1;
    while(k)
    {
        if(k&1) ans*=x;
        x*=x;
        k>>=1;
    }
    return ans;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n;i++)
    {
        cin >> v[i] >> w[i] >> l[i];
    }
    for (int i = 1; i <= n;i++)
    {
        int res = l[i];
        for (int k = 1; k <= res; res -= k, k *= 2)
        {
            for (int j = m; j >= v[i] * k;j--)
            {
                f[j] = max(f[j], f[j - v[i] * k] + w[i] * k);
            }
            
        }
        for (int j = m; j >= v[i] * res;j--)
            {
                f[j] = max(f[j], f[j - v[i] * res] + w[i] * res);
            }
    }
    cout << f[m] << endl;
    return 0;
}

01背包边界是 最后一个物品取或不取：取得话 就是f[i-1][j-v[i]]+w[i] 不取就是f[i-1][j]; 滚动数组实现 因为是一维 所以先小的被更改 但是要用到原先的数据 所以从大到小枚举
完全背包边界是 最后一个物品取或不去 取得话 就是f[i][j-v[i]]+w[i] 不取就是f[i-1][j]; 也是滚动数组实现 因为是一维 但是 边界是用的第i个 所以从小到大枚举
多重背包easy 就是 把1类物品多个 看成多个一样的物品 比如 x个1 那就是 1 1 1 1...1 然后当作01背包来写
多重背包hard 就是 借助二进制分配（一个数字 肯定能用一堆2的次幂的数字来表示 比如 3=1+2 9=1+2+4+2