#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 1001000
#define M 1010
int f[N];
int w[M],c[M];
int n,m;

void mutipack(int w,int c,int amount){
	if (amount * c >= m){
		for (int i = c; i<=m; i++){
			f[i] = max(f[i - c] + w,f[i]);
		}
		return;
	}
	int k = 1;
	while (k <= amount){
		for (int i = m; i>= k*c; i--){
			f[i] = max(f[i],f[i - k*c] + k*w);
		}
		amount -= k;
		k <<= 1;
	}
	for (int i = m; i>=amount * c; i--){
		f[i] = max(f[i],f[i-amount*c] + amount*w);
	}
	return;
}

int main(){
	while (scanf("%d",&m) != EOF){
		scanf("%d",&n);
		for (int i = 1; i<=n; i++){
			scanf("%d%d",&c[i],&w[i]);
		}	
		memset(f,0,sizeof(f));
		f[0] = 0;
		for (int i = 1; i<=n; i++){
			mutipack(w[i],w[i],c[i]);
		}
		printf("%d\n",f[m]);
	}
	return 0;	
}

• Re:贴个代码~~~94MS (990) hzoi_hexing 2014-01-17 20:29:00