作者在 2008-08-22 11:57:56 发布以下内容
着道题看起来是一个三维的背包问题,但是注意一个条件,就是每个组件只能放在地x到第x+w的位子上所以这时问题就可以简化复杂度,即只对第i个组件在第x位置上时的价值为j时的f最大值求解。
方程为
f[i][L][C]=max{f[i-1][L][C],f[i-1][L-w][C-c]+F[i]且L-w=x};
还要注意个地方就是dp的顺序，x越小越i值越小
#include <iostream> #include <algorithm> using namespace std; int l,n,b; //int x,w,f,c; int F[1001][10001]; const int INF=10000000; struct node { int x; int w; int f; int c; }; node Q[10001]; bool __inline cmp(node a,node b) { if(a.x<b.x) return 1; return 0; } void dp() { int i,j,k; //scanf("%d%d%d%d",&x,&w,&f,&c); for(k=0;k<n;k++) { i=Q[k].w+Q[k].x; for(j=b;j>=Q[k].c;j--) { if(F[i][j]<F[i-Q[k].w][j-Q[k].c]+Q[k].f) F[i][j]=F[i-Q[k].w][j-Q[k].c]+Q[k].f; } } return ; } void init() { int i,j; for( i=0;i<=b;i++) { F[0][i]=0; //F[i][0]=0; } for(j=1;j<=l;j++) for(i=1;i<=b;i++) F[j][i]=-INF; } int main() { scanf("%d%d%d",&l,&n,&b); init(); for(int i=0;i<n;i++) scanf("%d%d%d%d",&Q[i].x,&Q[i].w,&Q[i].f,&Q[i].c); sort(Q,Q+n,cmp); dp(); if(F[l][b]>0) printf("%d\n",F[l][b]); else printf("-1\n"); return 0; }
