多重背包问题，用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
#include
#include
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
#include
#include
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
#include
#include
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
#include
#include
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]] &