> 比较特别的是这题的cost和weight是一回事。所以函数的形参还可以少一个。
用背包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～ (1210) tanmingwei 2010-02-12 15:46:30
  • Re:按照《背包9讲》的伪代码，多重背包，1次AC，注意f[i]初始化为0～ (41) itsyarkee 2010-07-21 13:45:43
• Re:按照《背包9讲》的伪代码，多重背包，1次AC，注意f[i]初始化为0～ (1210) pangmm 2010-08-18 15:32:22