多重背包问题。将ni拆分成1，2，4，...，2^(k-1)，ni-2^k+1，易证这种拆分可以组合出1..ni之间的所有数字。于是转化成01背包求解。
以下是我的代码：
/*
* Author: lee1r
* Created Time: 2011/8/9 10:20:19
* File Name: poj1276.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-8);
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(10007);
const int kMaxm(100007);
int n,m,cnt,w[kMaxn],c[kMaxn],d[kMaxm];
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d",&m)==1)
{
cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int ni,wi;
scanf("%d%d",&ni,&wi);
for(int i=1;i<=ni;ni-=i,i<<=1)
{
cnt++;
w[cnt]=wi*i;
c[cnt]=wi*i;
}
if(ni>0)
{
cnt++;
w[cnt]=wi*ni;
c[cnt]=wi*ni;
}
}
int ans(0);
memset(d,0,sizeof(d));
for(int i=1;i<=cnt;i++)
for(int j=m;j>=c[i];j--)
d[j]=max(d[j],d[j-c[i]]+w[i]);
for(int i=0;i<=m;i++)
ans=max(ans,d[i]);
printf("%d\n",ans);
}
return 0;
}
posted on 2011-08-09 10:38
lee1r 阅读(325)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划