题目链接：P1064 金明的预算方案
简要分析：
将每个主件和附件进行组合，然后做分组背包 坑点：
附件有可能比主件更早出现 编号实际是指行数，而非第几个组件
代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=
10000;
int F[maxn*
1000],v[
100][
5],c[
1010][
5];
//c[]指代价，w[]指价值,T[]指第k组的件数
int T1[
100][
5],T2[
100][
5];
int N,V;
inline long long Read(
void)
{
int w=
0,x=
0;
char ch=
0;
while(!isdigit(ch))w|=ch==
'-',ch=
getchar();
while(isdigit(ch)) x=x*
10+(ch^
48),ch=
getchar();
return w?-
x:x;
}
int main(
void)
{
V=Read(),N=Read();
//输入
for(
int i=
1; i<=N; ++i) T1[i][
0]=
1;
for(
int i=
1; i<=N; ++
i)
{
int t1=Read(),t2=Read(),t3=Read();
//t1为价格，t2为重要的，t3为组别
if(t3==
0)
//主件
{
T1[i][1]=
t1;
T2[i][1]=t2*
t1;
}
else
{
T1[t3][0]++
;
T1[t3][T1[t3][0]]=
t1;
T2[t3][T1[t3][0]]=t2*
t1;
}
}
for(
int k=
1; k<=N; ++
k)
{
for(
int i=
1; i<=T1[k][
0]; ++
i)
{
if(i==
1)
{
c[k][++c[k][
0]]=
T1[k][i];
v[k][c[k][0]]=
T2[k][i];
}
else
{
int now=c[k][
0];
for(
int j=
1; j<=now; ++
j)
{
c[k][++c[k][
0]]=c[k][j]+
T1[k][i];
v[k][c[k][0]]=v[k][j]+
T2[k][i];
}
}
}
}
for(
int k=
1; k<=N; ++
k)
{
for(
int j=V; j>=
0; --
j)
{
for(
int i=
1; i<=c[k][
0]; ++i)
//第k组第i种方案
{
if(j>=
c[k][i])
F[j]=max(F[j],F[j-c[k][i]]+
v[k][i]);
}
}
}
printf("%d",F[V]);
return 0;
}
