这是一道依赖背包问题。
背包问题通常的解法都是由0/1背包拓展过来的，这道也不例外。
我最初想到的做法是，由于有依赖关系，先对附件做个DP，得到1-w的附件背包结果f[i]表示i花费得到的最大收益，然后把每个f[i]看成花费为i+c[i]，收益为f[i]的物品依次做0/1背包。
显然，问题是物品数目过多，复杂度为w*w，无法承受。
同时，此问题的主件收益为0这一点也需要细加考虑，由于主件收益为0，其实际上对每个附件方案的影响只有花费+c[i]，这样考虑下来我们只需要对附件进行DP，然后附加上+c[i]的影响即可。
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<iomanip> #include<algorithm> #include<cmath> #include<vector> #include<set> #include<map> #include<cstdlib> using namespace std; #define ll long long #define up(i,j,k) for(int i=(j);i<=(k);i++) #define cmin(a,b) a=min(a,b) #define cmax(a,b) a=max(a,b) #define pii pair<int,int> const int maxn=101000,inf=1e9,mod=9901; int read(){ int ch=getchar(),x=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return f*x; } int n,w; int f[maxn],g[maxn],p[55],m[55]; int c[15],v[15]; int main(){ freopen("chad.in","r",stdin); freopen("chad.out","w",stdout); while(scanf("%d%d",&n,&w)!=EOF){ memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); up(i,1,n){ scanf("%d%d",&p[i],&m[i]); up(j,1,m[i]){ scanf("%d%d",&c[j],&v[j]); for(int k=w;k>=c[j];k--) g[k]=max(g[k-c[j]]+v[j],g[k]); } up(j,p[i],w)f[j]=max(f[j],g[j-p[i]]); memcpy(g,f,sizeof(f)); } printf("%d ",f[w]); } return 0; }
事实上，第一种方法也是可行的，只不过，需要先对g数组进行一个（小优化）。
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<iomanip> #include<algorithm> #include<cmath> #include<vector> #include<set> #include<map> #include<cstdlib> using namespace std; #define ll long long #define up(i,j,k) for(int i=(j);i<=(k);i++) #define cmin(a,b) a=min(a,b) #define cmax(a,b) a=max(a,b) #define pii pair<int,int> const int maxn=101000,inf=1e9,mod=9901; int read(){ int ch=getchar(),x=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return f*x; } int n,w; int f[maxn],g[maxn],p[55],m[55]; int c[15],v[15],head,q[maxn]; int main(){ freopen("chad.in","r",stdin); freopen("chad.out","w",stdout); while(scanf("%d%d",&n,&w)!=EOF){ memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); up(i,1,n){ scanf("%d%d",&p[i],&m[i]); memset(g,0,sizeof(g)); up(j,1,m[i])scanf("%d%d",&c[j],&v[j]); up(j,1,m[i])for(int k=w;k>=c[j];k--) g[k]=max(g[k-c[j]]+v[j],g[k]); head=0; for(int j=0;j<=w;j++) if(!j||g[j]!=g[j-1])q[++head]=j; for(int j=w;j>=p[i];j--){ for(int k=1;q[k]+p[i]<=j&&k<=head;k++) f[j]=max(f[j],f[j-p[i]-q[k]]+g[q[k]]); } } printf("%d ",f[w]); } return 0; }