多重背包問題，用n個物品，每個物品有價值v[i]，每個物品數量限制為num[i]。
這道題是問，用所有的硬幣能夠在m的范圍內最多可以組合成多少種價值。
對於每個硬幣而言:
IF 價值×數量>=m
THEN 取這個硬幣的次數相當於無限制，可以考慮成完全背包
ELSE
THEN 考慮成0-1背包（二進制優化），就是把這個硬幣的v和num組合出0-1背包可能出現的狀態（可以去看背包九講）
（對於num，類似於編碼。 當2^n <=num/2時：k = 2^n（n=0，1，2，……）表示狀態，對應下來就是二進制的某一位數是1，然後還有一個狀態就是k>num/2的時候啦，num+1-k，這樣下來就可以用k來組合枚舉出從1->num的所有可能了。然後對於k，單位價值和大小都乘上k之後就變成了一個0-1背包）
AC代碼
[cpp]
#include <cstdio>
#include <cstdlib>
#include <cstring>
const int maxv=100001;
const int maxn=101;
int v[maxn],num[maxn];
int knap[maxv];
int n,m;
void multipleSack(int v,int num)
{
int i,j,k;
int space;
if(v*num>=m)
{
//用完全背包去求
for(space=v;space<=m;space++)
{
knap[space]=knap[space]|knap[space-v];
}
}
//用01背包去求，二進制優化
for(k=1;k<=num/2;k=(k<<1))
{
for(space=m;space>=k*v;space--)
{
knap[space]=knap[space]|knap[space-k*v];
}
}
k=num+1-k;
for(space=m;space>=k*v;space--)
{
knap[space]=knap[space]|knap[space-k*v];
}
return ;
}
int main()
{
int i,j,k,t;
while(~scanf("%d%d",&n,&m),n&&m)
{
for(i=1;i<=n;i++)
{
scanf("%d",&v[i]);
}
for(i=1;i<=n;i++)
{
scanf("%d",&num[i]);
}
memset(knap,0,sizeof(knap));
knap[0]=1;
for(i=1;i<=n;i++)
{
multipleSack(v[i],num[i]);
}
for(i=1,t=0;i<=m;i++)
{
t+=knap[i];
}
printf("%d\n",t);
}
return 0;
}
#include <cstdio>
#include <cstdlib>
#include <cstring>
const int maxv=100001;
const int maxn=101;
int v[maxn],num[maxn];
int knap[maxv];
int n,m;
void multipleSack(int v,int num)
{
int i,j,k;
int space;
if(v*num>=m)
{
//用完全背包去求
for(space=v;space<=m;space++)
{
knap[space]=knap[space]|knap[space-v];
}
}
//用01背包去求，二進制優化
for(k=1;k<=num/2;k=(k<<1))
{
for(space=m;space>=k*v;space--)
{
knap[space]=knap[space]|knap[space-k*v];
}
}
k=num+1-k;
for(space=m;space>=k*v;space--)
{
knap[space]=knap[space]|knap[space-k*v];
}
return ;
}
int main()
{
int i,j,k,t;
while(~scanf("%d%d",&n,&m),n&&m)
{
for(i=1;i<=n;i++)
{
scanf("%d",&v[i]);
}
for(i=1;i<=n;i++)
{
scanf("%d",&num[i]);
}
memset(knap,0,sizeof(knap));
knap[0]=1;
for(i=1;i<=n;i++)
{
multipleSack(v[i],num[i]);
}
for(i=1,t=0;i<=m;i++)
{
t+=knap[i];
}
printf("%d\n",t);
}
return 0;
}
這個在POJ上過不了，再來一段在POJ上可以過的代碼。
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
bool can_pay[100005];
int use_ai[100005];
int Ai[105], Ci[105];
int n, m, ans;
int coins()
{
int i, j;
ans = 0;
for(i = 0; i < n; ++i)
{
memset(use_ai, 0, sizeof(use_ai));
for(j = Ai[i]; j <= m; ++j)
{
if(!can_pay[j] && can_pay[j - Ai[i]] && use_ai[j - Ai[i]] < Ci[i])
{
can_pay[j] = true;
use_ai[j] = use_ai[j - Ai[i]] + 1;
++ans;
}
}
}
printf("%d\n", ans);
return 0;
}
int main()
{
int i;
while(scanf("%d%d", &n, &m), n || m)
{
memset(can_pay, false, sizeof(can_pay));
can_pay[0] = true;
for(i = 0; i < n; ++i)
scanf("%d", &Ai[i]);
for(i = 0; i < n; ++i)
scanf("%d", &Ci[i]);
coins();
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
bool can_pay[100005];
int use_ai[100005];
int Ai[105], Ci[105];
int n, m, ans;
int coins()
{
int i, j;
ans = 0;
for(i = 0; i < n; ++i)
{
memset(use_ai, 0, sizeof(use_ai));
for(j = Ai[i]; j <= m; ++j)
{
if(!can_pay[j] && can_pay[j - Ai[i]] && use_ai[j - Ai[i]] < Ci[i])
{
can_pay[j] = true;
use_ai[j] = use_ai[j - Ai[i]] + 1;
++ans;
}
}
}
printf("%d\n", ans);
return 0;
}
int main()
{
int i;
while(scanf("%d%d", &n, &m), n || m)
{
memset(can_pay, false, sizeof(can_pay));
can_pay[0] = true;
for(i = 0; i < n; ++i)
scanf("%d", &Ai[i]);
for(i = 0; i < n; ++i)
scanf("%d", &Ci[i]);
coins();
}
return 0;
}
