Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 代码不错，赞！

Posted by lpl1998 at 2014-08-15 08:31:16 on Problem 1276
In Reply To:背包九讲二进制思想优化（代码还算干净） Posted by:a798253982 at 2013-08-11 17:46:15
```> #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;
> }
```

Followed by: