三种基础背包

荼白 · 2020-10-15 17:55:45 · 个人记录

#include <iostream>
#include <vector>
using namespace std;
int dp[1005];
int v,w,s;//v是价值，w是重量，s是数量
int n,V;
struct Good
{
    int w;
    int v;
};
void f1()//01背包
{
    for(int j=V;j>=w;j--)
        dp[j]=max(dp[j],dp[j-w]+v);
}
void f2()//完全背包
{
    for(int j=w;j<=V;j++)
        dp[j]=max(dp[j],dp[j-w]+v);
}
void f3()//多重背包
{
    vector<Good> goods;
        for(int k=1;k<=s;k<<=1)
        {
            s-=k;
            goods.push_back({k*w,k*v});
        }
        if(s>0) goods.push_back({s*w,s*v});
    for(auto good:goods)
    {
        for(int j=V;j>=good.w;j--)
            dp[j]=max(dp[j],dp[j-good.w]+good.v);
    }
}
int main()
{
    cin >> n >> V;
    for(int i=0;i<n;i++)
    {
        cin >> w>> v>> s;
        if(s==-1) f1();
        else if(s==0) f2();
        else if(s>0) f3();
    }
    cout << dp[V];
    return 0;
}