http://acm.pku.edu.cn/JudgeOnline/problem?id=1276將第i種面額分成若干面額的bill，這些bill面額為 系數(shù)1，2，4，。。。。2^(k-1),n[i]-2^k+1 分別乘以d[i] ， 并且n[i]-2^k+1>0;
(我也是看別人的，找個數(shù)試一下就知道了，用這些面額系數(shù)就可以，就可以組成<=n[i]的所有可能)
O(V*
S log n[i])
f[v]表示容量v所能得到的總數(shù)
簡化方程: f[v]=max{f[v],f[v-c]+c}
f[]初始都為0
多重背包 詳見
背包九講
#include<iostream>
using namespace std;
#define MAXN 120005 //maxcash
#define MAX 11
int n[MAX],d[MAX];
int f[MAXN];
int V,N;
void ZeroOnePack(int c){
for(int v=V;v>=c;--v){
f[v]=max(f[v],f[v-c]+c);
}
return;
}
void CompletePack(int c){
for(int v=c;v<=V;++v){
f[v]=max(f[v],f[v-c]+c);
}
return;
}
void MultiplePack(int c,int amount){
if(c*amount>=V){
CompletePack(c);
return;
}
int k=1;
while(k<amount){
ZeroOnePack(k*c);
amount-=k;
k*=2;
}
ZeroOnePack(amount*c);
return;
}
int main()
{
int a,b;
while(scanf("%d%d",&V,&N)!=EOF){
if(!V&&!N)continue;
int flag=0;
for(int i=0;i<=V;++i)f[i]=0;
// memset(f,0,sizeof(f));
for(int i=0;i<N;++i){
scanf("%d%d",&a,&b);
n[i]=a,d[i]=b;
if(d[i]==V){f[V]=V;flag=1;}
}
if(V==0)f[V]=0,flag=1;
if(!flag){
for(int i=0;i<N;++i)
if(n[i]&&d[i]<=V)
MultiplePack(d[i],n[i]);
}
printf("%d\n",f[V]);
}
return 0;
}posted on 2009-03-18 22:42
爬 閱讀(1418)
評論(2) 編輯 收藏 引用 所屬分類:
Dynamic programming