Posted on 2008-08-02 19:35
oyjpart 閱讀(2873)
評論(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;
}