#include <cstdio>
#include <cstring>
#define Max(a,b) (a)>(b)?(a):(b)

int dp[100001],Cost[11],Count[11],cash;

void ZeroOnePack(int cost){
	int i;
	for(i=cash;i>=cost;i--)
	    dp[i]=Max(dp[i],dp[i-cost]+cost);
}

void CompletePack(int cost){
	int i;
	for(i=cost;i<=cash;i++)
	    dp[i]=Max(dp[i],dp[i-cost]+cost);
}

void MultiplePack(int cost,int count){
	if(cost*count > cash)
	    CompletePack(cost);
	else{
		int k=1;
		while(k < count){
			ZeroOnePack(k*cost);
			count -= k;
			k *= 2;
		}
		ZeroOnePack(count*cost);
	}
}


int main(){
	int n,i,j,k;
	while(~scanf("%d%d",&cash,&n)){
		for(i=1;i<=n;i++)
			scanf("%d%d",&Count[i],&Cost[i]);			
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++)
			MultiplePack(Cost[i],Count[i]);
		printf("%d\n",dp[cash]);
	}
	return 0;
}

• 代码不错，赞！ (911) lpl1998 2014-08-15 08:31:16
• Re:背包九讲二进制思想优化（代码还算干净） (911) sun1583353326 2019-04-17 17:20:52