分组背包

分组背包是LC(01)背包的一种变形吧。它就是给你一点质量，你不一定全部质量都要选，可以看看HDUOJ的Saving HDU，如果用01背包算出来就是3，用分组背包或者贪心算出来就是5
模板

//n为物品种类，v是背包容量，pi为物品价格，m为物品质量
//前面的i也得是1，不能是0
for(int i=1;i<=n;i++){
    for(int j=v;j>=0;j--){
        for(int k=1;k<=m[i];k++){
            int t1=k,t2=k*pi[i];
            if(j<k)
                continue;
            dp[j]=max(dp[j],dp[j-t1]+t2);
        }
    }
}
cout<<dp[v];

 

Title

某一水题

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,t,w1[1000001],w2[1000001],t1[1000001],t2[1000001],dp[1000001];
int main(){
    cin>>n>>t;
    for(int i=0;i<n;i++)
        cin>>w1[i]>>t1[i]>>w2[i]>>t2[i];
    for(int i=0;i<n;i++)
        for(int j=t;j>=min(t1[i],t2[i]);j--){
            if(t1[i]<=j)
                dp[j]=max(dp[j],dp[j-t1[i]]+w1[i]);
            else 
                dp[j]=max(dp[j],dp[j-t2[i]]+w2[i]);
        }
    cout<<dp[t];
    return 0;
}