看了這么多天的背包，總算漸漸開始理解了。
背包問題有很多種，基本的有兩種：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
小鼠標 閱讀(167)
評論(0) 編輯 收藏 引用 所屬分類:
DP