多重背包问题, 参考<<背包问题9讲>>
#include <iostream>
using namespace std;
const int MAXN = 120005;
const int MAX = 15;
int c[MAX] , n[MAX];
int f[MAXN];
int N,V;
inline int max(int a, int b)
{
return a>b? a: b;
}
void ZeroOnePack(int c, int w){
for(int v=V; v>=c; v--)
f[v] = max(f[v], f[v-c]+w);
return;
}
void CompletePack(int c, int w){
for(int v=c; v<=V; ++v)
f[v] = max(f[v], f[v-c]+w);
return;
}
void MultiplePack(int c, int w, int m){
if(m*c>=V){
CompletePack(c, w);
return ;
}
int k=1;
while(k<m){
ZeroOnePack(k*c, k*w);
m -= k;
k*=2;
}
ZeroOnePack(m*c, m*w);
return ;
}
int main(){
int i;
while(cin>>V&&cin>>N){
if(!V&&!N) continue;
for(i=0; i<=V; ++i) f[i]=0;
for(i=1; i<=N; ++i)
cin>>n[i]>>c[i];
for(i=1; i<=N; ++i)
MultiplePack(c[i], c[i], n[i]);
cout<<f[V]<<endl;
}
return 0;
}posted on 2010-12-23 11:05
小阮 阅读(152)
评论(0) 编辑 收藏 引用 所属分类:
POJ