Algoogle

Algorithm for Programming Contest

AOJ 2354 Fractional Knapsack

Category: AOJ Tag: greedy

Fractional Knapsack

問題概要


解法


値が全部正なら[0,1]の範囲をかければ隙間なく埋められるのでv/wの比が大きいものから
貪欲に選んでいけば良さそうなのでw,vのいずれかが負の場合を考える.

w<=0, v>=0なら重さを減らしつつ価値を上げられるので選ぶべき.
w>=0, v<=0なら重くなりつつ価値が下がるので無視するべき.
w<=0, v<=0ならそこではそれを使うべきか分からない.
一度使ったことにして, あとで使わないかどうかを決めればいい.
使わないかどうか決めるのは, どちらも符号反転してやれば
使うかどうか(正の時と同じ)でできる.

コード


(2354.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>

#define rep(i,a) for(int i = 0;i < (a); i++)
#define rall(u) (u).rbegin(),(u).rend()
#define pb push_back
#define EPS 1e-10

using namespace std;
struct S{
    int w, v;
    S(int w, int v):w(w),v(v){}
    bool operator<(const S &s) const{
        return s.w * v < w * s.v;
    }
};

int main(){
    double N, W, ans = 0;
    cin >> N >> W;
    vector<S> p;
    rep(i,N){
        int w, v;
        cin >> w >> v;
        if(w <= 0 && v >= 0){
            ans += v;
            W -= w;
        }
        else if(w >= 0 && v <= 0) continue;
        else if(w < 0 && v < 0){
            ans += v; W -= w;
            p.pb(S(-w,-v));
        }
        else p.pb(S(w,v));
    }
    sort(rall(p));

    rep(i,p.size()){
        int tw = p[i].w, tv = p[i].v;
        double x = min(1.0, W/tw);
        ans += x * tv;
        W -= x * tw;
        if(W < EPS) break;
    }
    printf("%.8f\n",ans);
    return 0;
}

Comments