HDU 5445 Food Problem(多重背包+二进制优化)

时间:2021-12-25 00:54:03

http://acm.hdu.edu.cn/showproblem.php?pid=5445

题意:
现在你要为运动会提供食物,总共需要提供P能量的食物,现在有n种食物,每种食物能提供 t 能量,体积为 u ,并且最多能提供 v 的数量。运载食物的卡车有m种,每种能提供 x 的运输空间,运输花费为 y,最多可以雇佣 z 辆车。食物可以切割后运输。不需要整块一起运输,但只有一整块全部到达时才能提供能量。

现在需要计算出最少需要多少花费。

思路:

因为食物可以切割运输,那么食物的总体积肯定是越小越好,所以先用多重背包计算出提供P能量所需的最少食物体积,食物的能量最多能提供100,所以背包容量到P+100即可。

有了体积之后,接下来只需要计算运输这些体积的食物最少需要多少花费,再用一次多重背包即可。

需要使用二进制优化。

 #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f; int n,m,p,tot;
int val[],cost[];
int dp[]; int solve1()
{
for(int i=;i<=p+;i++) dp[i] = INF;
dp[] = ;
for(int i=;i<tot;i++)
for(int j=p+;j>=val[i];j--)
dp[j] = min(dp[j],dp[j-val[i]]+cost[i]);
int ans = INF;
for(int i=p;i<=p+;i++)
ans = min(ans, dp[i]);
return ans;
} int solve2(int v)
{
memset(dp,,sizeof dp);
for(int i=;i<tot;i++)
for(int j=;j>=cost[i];j--)
dp[j] = max(dp[j],dp[j-cost[i]]+val[i]);
for(int i=;i<=;i++)
if(dp[i]>=v) return i;
return INF;
} int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&p);
tot = ;
for(int i=;i<=n;i++)
{
int t,u,v;
scanf("%d%d%d",&t,&u,&v);
for(int k=;v;k<<=)
{
int num = min(k,v);
val[tot] = num*t;
cost[tot++] = num*u;
v -= num;
}
}
int v = solve1();
tot = ;
for(int i=;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
for(int k=;z;k<<=)
{
int num = min(k,z);
cost[tot] = num*y;
val[tot++] = num*x;
z -= num;
}
}
if(v==INF) {puts("TAT");continue;}
int ans = solve2(v);
if(ans==INF) puts("TAT");
else printf("%d\n",ans);
}
return ;
}