【多重背包模板】poj 1014

时间:2022-11-10 05:57:53
#include <iostream>
#include <stdio.h>
#include <cstring>
#define INF 100000000
using namespace std;
int f[]; //f[j]相当于f[i][j]: 考虑1...i个物品,恰好放到容量为j,所能达到的最大价值
int v; //背包容量
void complete_pack(int *dp, int c, int w)
{
for(int i = c; i <= v; i++)
dp[i] = max(dp[i], dp[i - c] + w);
}
void zeroone_pack(int *dp, int c, int w)
{
for(int i = v; i >= c; i--)
dp[i] = max(dp[i], dp[i - c] + w);
} void mutiple_pack(int *dp, int c, int w, int m)
{
if(c * m >= v)
{
complete_pack(dp, c, w);
return;
}
int k = ;
while(k < m)
{
zeroone_pack(dp, k * c, k * w);
m = m - k;
k = * k;
}
zeroone_pack(dp, c * m, w * m);
}
int main()
{
//freopen("in.txt","r",stdin);
int sum, i, c[], w[], m[],cas = ;
while(scanf("%d%d%d%d%d%d",&m[],&m[],&m[],&m[],&m[],&m[]))
{
if(m[]== && m[]== && m[]== && m[]== && m[]== && m[]==)
break;
sum = ;
for(i = ; i <= ; i++)
{
c[i] = w[i] = i;
sum += c[i] * m[i];
}
printf("Collection #%d:\n", ++cas);
if(sum & )
puts("Can't be divided.\n");
else
{
sum /= ;
v = sum;
for(i = ; i <= sum; i++)
f[i] = -INF;
f[] = ;
for(i = ; i <= ; i++)
mutiple_pack(f, c[i], w[i], m[i]);
if(f[v] < )
puts("Can't be divided.\n");
else
puts("Can be divided.\n");
}
}
return ;
}