请问有用背包九讲7的算法写过的吗

写了好久，最后五个点超时。 代码如下 //背包九讲P07 #include #include using namespace std; struct main_item{ int w1,c1,num;//附件数量 }mt[100]; struct annex_item{ int w2,c2; }a[100][3]; int f[100][40000];//f[i][j]第i个物品组费用为j时最大价值 int opt[40000];//分组背包 int y[100];//每个物品组主件费用 int main() { int n,m; scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int v,p,q; scanf("%d%d%d",&v,&p,&q); if (q==0) { mt[i].w1=v; mt[i].c1=vp; } else { mt[q].num++; a[q][mt[q].num].w2=v; a[q][mt[q].num].c2=vp; } }//附件集合归类

int r=0;//物品组数量 for (int e=1;e<=m;e++) if (mt[e].w1!=0) { r++; y[r]=mt[e].w1;//主件费用 for (int i=1;i<=mt[e].num;i++) for (int j=n;j>=y[r];j--) if (j-y[r]>=a[e][i].w2) f[r][j]=max(f[r][j],f[r][j-a[e][i].w2]+a[e][i].c2); for (int i=y[r];i<=n;i++) f[r][i]+=mt[e].c1; }

for (int i=1;i<=r;i++) for (int j=n;j>=0;j--) for (int k=y[i];k<=j;k++) opt[j]=max(opt[j],opt[j-k]+f[i][k]); cout<<opt[n]<<endl; return 0; }