> 用背包9讲中的伪代码为什么老是Rumtime Error
> #include<stdio.h>
> #include<string.h>
> const int maxN = 11;
> const long maxcash = 100001;
> long cash;
> long f[maxcash+1];
> void zeroOnePack( long cost, long weight ) {
> 	long i;
> 	for ( i=cash; i>=cost; i-- ) {
> 		if(f[i]<f[i-cost]+weight)
> 			f[i] = f[i-cost] + weight;
> 	}
> }
> void completPack( long cost, long weight ) {
> 	long i;
> 	for( i=cost; i<=cash; i++ ) {
> 		if( f[i]<f[i-cost] + weight )
> 			f[i] = f[i-cost] + weight;
> 	}
> }
> void multiplePack ( long cost, long weight, long account) {
> 	int k;
> 	if( account*weight>=cash ) {
> 		completPack ( cost, weight);
> 	}
> 	else {
> 		k = 1;
> 		while ( k<account ) {
> 			zeroOnePack (k*cost, k*weight);
> 			k = k*2;
> 			account -= k;
> 		}
> 		zeroOnePack (account*cost,account*weight);
> 	}
> }
> int main() {
> 	long N, n[maxN], D[maxN], i;
> 	freopen( "input.in", "r", stdin);
> 	while( scanf("%ld%ld", &cash, &N)==2 ) {
> 		for ( i=1; i<=N; i++) {
> 			scanf("%ld%ld", &n[i], &D[i]);
> 		}
> 		memset(f, 0, sizeof(f));
> 		for ( i=1; i<=N; i++ ) {
> 			multiplePack (D[i],D[i],n[i]);
> 		}
> 		printf("%ld\n",f[cash]);
> 	}
> 	return 0;
> }

• Re:按照《背包9讲》的伪代码，多重背包，1次AC，注意f[i]初始化为0～ (41) itsyarkee 2010-07-21 13:45:43