P1064 金明的预算方案

思路：就是一个背包问题  因为数据范围小，所以不把 1个带附着物的东西 拆成 带1个带2个或不带

#include<bits/stdc++.h>
using namespace std;
const int maxn=30000+10;
int f[maxn];
int zhujianw[maxn],zhujianv[maxn],cijianw[maxn][3],cijianv[maxn][3];
int main(){
    int n,m;
    cin>>n>>m;
    int v,p,q;

for(int i=1;i<=m;i++){
    cin>>v>>p>>q;
    if(!q){
        zhujianw[i]=v,zhujianv[i]=v*p;		
    }
    else {
        cijianw[q][0]++;
        cijianw[q][cijianw[q][0]]=v;
        cijianv[q][cijianw[q][0]]=v*p;
    }

}

for(int i=1;i<=m;i++){
    for(int j=n;zhujianw[i]&&j>=zhujianw[i];j--){
        f[j]=max(f[j],f[j-zhujianw[i]]+zhujianv[i]);
        if(j>=zhujianw[i]+cijianw[i][1])
            f[j]=max(f[j],f[j-zhujianw[i]-cijianw[i][1]]+zhujianv[i]+cijianv[i][1]);
        if(j>=zhujianw[i]+cijianw[i][2])
    f[j]=max(f[j],f[j-zhujianw[i]-cijianw[i][2]]+zhujianv[i]+cijianv[i][2]);
    if(j>=zhujianw[i]+cijianw[i][1]+cijianw[i][2])
        f[j]=max(f[j],f[j-zhujianw[i]-cijianw[i][1]-cijianw[i][2]]+zhujianv[i]+cijianv[i][1]+cijianv[i][2]);
}
}
cout<<f[n]<<endl;
    return 0;
}