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 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: