有附件的背包的常规算法
#include<cstdio> #include<cstdlib> #include<vector> using namespace std; int m,n; const int M=32000,N=60; int f[N+3][M+3]; vector <int> son[N+3],ff[N+3]; vector <int> v,w; int main() { scanf("%d%d",&m,&n); int fa,vv,ww; v.push_back(0),w.push_back(0); for(int i=1;i<=n;i++) scanf("%d%d%d",&ww,&vv,&fa),son[fa].push_back(i),v.push_back(vv*ww),w.push_back(ww) ; int sz=son[0].size() ; for(int i=0;i<sz;i++) { int zj =son[0][i]; f[zj ][w[zj ]]=v[zj ]; int fj_sz=son[zj].size() ; for(int j=0;j<fj_sz;j++) { int fj=son[zj][j]; for(int k=m;k>=w[zj]+w[fj];k--) if(f[zj][k-w[fj]]) f[zj][k]=max(f[zj][k],f[zj][k-w[fj]]+v[fj]); } son[zj].clear() ; for(int k=m;k>=w[zj];k--) if(f[zj][k]) son[zj].push_back(++n),w.push_back(k),v.push_back(f[zj][k]); fj_sz=son[zj].size() ; for(int k=m;k>=w[zj];k--) for(int j=0;j<fj_sz;j++) { int fj=son[zj][j]; if(k>=w[fj]) f[0][k]=max(f[0][k],f[0][k-w[fj]]+v[fj]); } } printf("%d ",f[0][m]); return 0; }