背包DP专题

P1510 精卫填海

很容易看出这是个01背包，可是怎么转化模型呢？注意到，输出impossible的情况就是当体力值C不可以处理体积为V的石头的时候，很自然的想到：把体力值看作背包的体积，把石头的体积看作背包的权值。求最大剩余体力值->在背包体积尽可能小的情况下，背包的权值>=石头的体积V

	rd(V),rd(n),rd(C);
	rep(i,1,n){
		rd(w[i]),rd(v[i]);
	}
	rep(i,1,n)
		dwn(j,C,v[i])
			f[j]=max(f[j],f[j-v[i]]+w[i]);
	rep(i,1,C){
		if(f[i]>=V){
			printf("%d
",C-i);
			exit(0);
		}
	}
	printf("Impossible
");

• 二维费用背包

	rd(n),rd(M),rd(T);
	rep(i,1,n)rd(m[i]),rd(t[i]);
	rep(i,1,n)
		dwn(j,T,t[i])
			dwn(k,M,m[i])
				f[j][k]=max(f[j][k],f[j-t[i]][k-m[i]]+1);
	printf("%d",f[M][T]);