Posted on 2008-08-02 19:35
oyjpart 閱讀(2873)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
ACM/ICPC或其他比賽
Unlucky Luke!
By oyjpArt/alpc12
題意
n
有2個(gè)倉(cāng)庫(kù)，容量為(0 <= V <= 5000) 浮點(diǎn)數(shù)！
n
有100個(gè)物品，每個(gè)物品容量為(0 <= v[i] <= 100) 整數(shù) 價(jià)值為 m[i] (無(wú)范圍浮點(diǎn)數(shù)！)
n
現(xiàn)在把這些物品放到2個(gè)倉(cāng)庫(kù)中，求最大的價(jià)值。
n
如果有放不進(jìn)去的物品，可以切割出一部分放進(jìn)去，但是一旦切割，沒(méi)放進(jìn)進(jìn)去的一部分必須丟棄。
貪心？
n
這道題初看上去，很有讓人貪心的沖動(dòng)。
n
我和alpc42合計(jì)了一下。
n
根據(jù)A[i].m/A[i].v
作為優(yōu)先級(jí) 給(A, A+n)
排序。
n
依次將A[0],
A[1]…A[n-1]放入倉(cāng)庫(kù)，如果放不進(jìn)去了，則切掉。
n
現(xiàn)在有兩個(gè)倉(cāng)庫(kù)，當(dāng)準(zhǔn)備放一個(gè)物品進(jìn)去的時(shí)候，應(yīng)該放到哪個(gè)倉(cāng)庫(kù)呢？
第一次提交
n
我們倆想了想，覺(jué)得應(yīng)該是放到空閑地方大的倉(cāng)庫(kù)，因?yàn)橐M可能把性?xún)r(jià)比高的物品放進(jìn)去。
n
4144542008-08-01 13:42:41
n WrongAnswer
n
C++
第二次提交
n
隨后我想出了一種會(huì)讓程序出bug的情況。
n
就是當(dāng)兩個(gè)物品性?xún)r(jià)比相當(dāng)?shù)臅r(shí)候，應(yīng)該要讓大容量的在前面。因?yàn)橛锌赡苄∪萘康南确胚M(jìn)去，導(dǎo)致大容量的沒(méi)有地方放了，而需要切割。但實(shí)際上可以把小容量的放到小剩余容量的倉(cāng)庫(kù)里面去，而大容量的就可以放到大剩余容量的倉(cāng)庫(kù).
n
改正提交之后還是Wrong
Answer
問(wèn)題在這
n
思考了一下我發(fā)現(xiàn)其實(shí)上面那個(gè)bug并沒(méi)有解決。假設(shè)A[i].m/A[i].v > A[j].m/A[j].v，按理來(lái)說(shuō)應(yīng)該先放i，再放j。但是加入A[i].v
< A[j].v,同樣的有可能先放i再放j會(huì)讓j被迫切割。
n
那么怎么辦？
n
隨后我們想到了一種動(dòng)態(tài)規(guī)劃的方法，但是因?yàn)閺?fù)雜度太高，放棄了。這時(shí)候我們發(fā)現(xiàn)手頭有很多題目可以做，就沒(méi)有再做這個(gè)題目了。
賽后的思考
n
之所以會(huì)出現(xiàn)這樣的問(wèn)題。在于我們最開(kāi)始的假設(shè)：要把性?xún)r(jià)比高的物品放到容量更大的倉(cāng)庫(kù)中。
n
那么，假如我們枚舉一個(gè)物品放到A倉(cāng)庫(kù)還是B倉(cāng)庫(kù)的話，就可以解決這個(gè)問(wèn)題了。
n
所謂枚舉，其實(shí)是一個(gè)動(dòng)態(tài)規(guī)劃。
n
設(shè)dp[i][j] 代表前i個(gè)物品(排序后)都被完全放入了倉(cāng)庫(kù)，并且A倉(cāng)庫(kù)已經(jīng)裝了j的容量的物品。顯然我們可以同時(shí)知道B倉(cāng)庫(kù)的容量是多少。
n
向后推的狀態(tài)方程
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
如果一個(gè)倉(cāng)庫(kù)已經(jīng)放不進(jìn)去了，大家可以想想，應(yīng)該是把下一個(gè)物品切割掉放入這個(gè)倉(cāng)庫(kù)中。（如果后面有物品可以放到另外一個(gè)倉(cāng)庫(kù)中，不用擔(dān)心。后面的DP會(huì)覆蓋這種情況）
n
一個(gè)倉(cāng)庫(kù)放滿了之后，另外一個(gè)倉(cāng)庫(kù)堆放的情況其實(shí)就是貪心了。
// 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;
}