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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

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

Posted by a798253982 at 2013-08-11 17:46:15 on Problem 1276
#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