看了这么多天的背包，总算渐渐开始理解了。
背包问题有很多种，基本的有两种：0-1背包和完全背包。多重背包可由这两种组合得来。
本题是多重背包问题，可以简单的将多重背包直接转化为0-1背包来求解，但是这种转化很有可能导致超时，因为物品数量太多了。可行的办法是利用 二进制状态压缩，这样可以大大减少物品数量（实际物品数量只有log（N）件）。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define LENN 12
#define LENF 100010
int cash, N;
int n[LENN], D[LENN];
int f[LENF];
int max(int a, int b)
{
if(a > b)
return a;
return b;
}
void MPack()//MultiplePack
{
int i, j;
for(i = 0; i <= cash; i++)
f[i] = 0;
for(i = 0; i < N; i++)
{
if(n[i] * D[i] >= cash)//completePack
{
for(j = D[i]; j <= cash; j++)
f[j] = max(f[j], f[j - D[i]] + D[i]);
}
else//ZeroOnePack
{
int k = 1;
int M = n[i];
while(k < M)
{
for(j = cash; j >= k * D[i]; j--)
{
f[j] = max(f[j], f[j - k * D[i]] + k * D[i]);
}
M -= k;
k *= 2;
}
for(j = cash; j >= M * D[i]; j--)
f[j] = max(f[j], f[j - M * D[i]] + M * D[i]);
}
}
}
int main()
{
int i, j;
while(scanf("%d", &cash) == 1)
{
scanf("%d", &N);
for(i = 0; i < N; i++)
scanf("%d%d", &n[i], &D[i]);
if(cash != 0 && N != 0)
{
MPack();
printf("%d\n", f[cash]);
}
else
printf("0\n");
}
}
posted on 2012-05-09 09:51
小鼠标 阅读(142)
评论(0) 编辑 收藏 引用 所属分类:
DP