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

Re:背包九讲二进制思想优化(代码还算干净)

Posted by sun1583353326 at 2019-04-17 17:20:52 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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator