Posted on 2008-08-02 19:35
oyjpart 阅读(2865)
评论(0) 编辑 收藏 引用 所属分类:
ACM/ICPC或其他比赛
Unlucky Luke!
By oyjpArt/alpc12
题意
n
有2个仓库，容量为(0 <= V <= 5000) 浮点数！
n
有100个物品，每个物品容量为(0 <= v[i] <= 100) 整数 价值为 m[i] (无范围浮点数！)
n
现在把这些物品放到2个仓库中，求最大的价值。
n
如果有放不进去的物品，可以切割出一部分放进去，但是一旦切割，没放进进去的一部分必须丢弃。
贪心？
n
这道题初看上去，很有让人贪心的冲动。
n
我和alpc42合计了一下。
n
根据A[i].m/A[i].v
作为优先级 给(A, A+n)
排序。
n
依次将A[0],
A[1]…A[n-1]放入仓库，如果放不进去了，则切掉。
n
现在有两个仓库，当准备放一个物品进去的时候，应该放到哪个仓库呢？
第一次提交
n
我们俩想了想，觉得应该是放到空闲地方大的仓库，因为要尽可能把性价比高的物品放进去。
n
4144542008-08-01 13:42:41
n WrongAnswer
n
C++
第二次提交
n
随后我想出了一种会让程序出bug的情况。
n
就是当两个物品性价比相当的时候，应该要让大容量的在前面。因为有可能小容量的先放进去，导致大容量的没有地方放了，而需要切割。但实际上可以把小容量的放到小剩余容量的仓库里面去，而大容量的就可以放到大剩余容量的仓库.
n
改正提交之后还是Wrong
Answer
问题在这
n
思考了一下我发现其实上面那个bug并没有解决。假设A[i].m/A[i].v > A[j].m/A[j].v，按理来说应该先放i，再放j。但是加入A[i].v
< A[j].v,同样的有可能先放i再放j会让j被迫切割。
n
那么怎么办？
n
随后我们想到了一种动态规划的方法，但是因为复杂度太高，放弃了。这时候我们发现手头有很多题目可以做，就没有再做这个题目了。
赛后的思考
n
之所以会出现这样的问题。在于我们最开始的假设：要把性价比高的物品放到容量更大的仓库中。
n
那么，假如我们枚举一个物品放到A仓库还是B仓库的话，就可以解决这个问题了。
n
所谓枚举，其实是一个动态规划。
n
设dp[i][j] 代表前i个物品(排序后)都被完全放入了仓库，并且A仓库已经装了j的容量的物品。显然我们可以同时知道B仓库的容量是多少。
n
向后推的状态方程
n
dp[i+1][j+A[i+1].v] =
Max(dp[i+1][j+A[i+1].v], dp[i][j] + A[i+1].m);
n
dp[i+1][j] = Max(dp[i+1][j], dp[i][j] +
A[i+1].m);
n
如果一个仓库已经放不进去了，大家可以想想，应该是把下一个物品切割掉放入这个仓库中。（如果后面有物品可以放到另外一个仓库中，不用担心。后面的DP会覆盖这种情况）
n
一个仓库放满了之后，另外一个仓库堆放的情况其实就是贪心了。
// Solution by alpc12
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 105;
const double EPS = 1e-7;
const double INF = 10e100;
double dp[N][10001], V;
int n, maxv, vall[N];
struct Node
{
int v;
double m;
};
bool operator<(const Node&a,const Node&b) {
return a.m/a.v > b.m/b.v;
}
Node A[N];
inline double Max(double a,double b) {
return a > b ? a : b;
}
inline double Min(double a,double b) {
return a < b ? a : b;
}
double go(double v, int st) {
double ans = 0;
while(v > 0 && st <= n) {
if(A[st].v <= v) {
v -= A[st].v;
ans += A[st].m;
} else {
ans += A[st].m * v/A[st].v;
v = 0;
}
st++;
}
return ans;
}
void solve() {
int i, j, k;
for(i = 0; i <= n; ++i)
for(j = 0; j <= maxv; ++j)
dp[i][j] = -INF;
dp[0][0] = 0;
double max = 0;
for(i = 0; i <= n; ++i) {
for(j = 0; j <= vall[i] && j <= V; ++j) if(dp[i][j] != -INF) {
max = Max(max, dp[i][j]);
if(i < n) {
int k = vall[i] - j;
if((V-j) >= A[i+1].v) {
dp[i+1][j+A[i+1].v] = Max(dp[i+1][j+A[i+1].v], dp[i][j] + A[i+1].m);
} else {
max = Max(max, dp[i][j] + A[i+1].m*(V-j)/A[i+1].v + go(V-k, i+2));
}
if((V-k) >= A[i+1].v) {
dp[i+1][j] = Max(dp[i+1][j], dp[i][j] + A[i+1].m);
} else {
max = Max(max, dp[i][j] + A[i+1].m*(V-k)/A[i+1].v + go(V-j, i+2));
}
}
}
}
printf("%.4lf\n", max);
}
int main()
{
//freopen("t.in", "r", stdin);
int ntc, i, j;
scanf("%d", &ntc);
while(ntc--) {
scanf("%d %lf", &n, &V);
maxv = 0;
for(i = 1; i <= n; ++i) {
scanf("%d", &(A[i].v));
maxv += A[i].v;
}
maxv = Min(maxv, (int)V);
for(i = 1; i <= n; ++i) {
scanf("%lf", &(A[i].m));
}
sort(A + 1, A + n + 1);
vall[0] = 0;
for(i = 1; i <= n; ++i) {
vall[i] = vall[i-1] + A[i].v;
}
solve();
}
return 0;
}