結果

問題 No.2167 Fibonacci Knapsack
コンテスト
ユーザー PCTprobability
提出日時 2022-12-19 04:51:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,145 bytes
コンパイル時間 2,265 ms
コンパイル使用メモリ 204,932 KB
最終ジャッジ日時 2025-02-09 16:34:41
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// ------------------------------------------8<------- start of library -------8<----------------------------------------------
template<class T>
class Knapsack {
public:
    const int size;
    vector<bool> opt_item;
    T capacity, opt_v;

    Knapsack(const int _n, const T _c) :
        size(_n), opt_item(_n, false), capacity(_c), n(0), item(_n), used(_n, false) {}
    void add_item(const int v, const int w) {
        item[n].v = v;
        item[n++].w = w;
    }

    T MaximumValue() {
        sort(item.begin(), item.end(),
             [](const Item &d1, const Item &d2) { return d1.v * d2.w > d2.v * d1.w; });

        opt_v = 0;
        for (int i = 0, w = 0; i < size; ++i) {
            if (w + item[i].w <= capacity) {
                w += item[i].w;
                opt_v += item[i].v;
                opt_item[i] = true;
            }
        }

        Rec(0, 0, 0);

        return opt_v;
    }

private:
    struct Item { T v , w; };
    int n;
    vector<Item> item;
    vector<bool> used;

    void Rec(int idx, T value, T weight) {
        if (idx == size || capacity <= weight) {
            if (weight <= capacity && opt_v < value) {
                opt_v = value;
                opt_item = used;
            }
            return ;
        }
        if (opt_v < value) {
            opt_v = value;
            opt_item = used;
        }

        // 線形緩和したときの目的関数値の計算
        double tmp_v = value, tmp_w = weight;
        int tmp_i;
        for (tmp_i = idx; tmp_w < capacity && tmp_i < size; ++tmp_i) {
            if (tmp_w + item[tmp_i].w <= capacity) {
                tmp_v += item[tmp_i].v;
                tmp_w += item[tmp_i].w;
            }
            else if (tmp_w + item[tmp_i].w == capacity) {
                // 緩和解が元の実行可能解
                tmp_v += item[tmp_i].v;
                if (opt_v < tmp_v) {
                    opt_v = tmp_v;
                    opt_item = used;
                    for (int i = idx; i <= tmp_i; ++i)
                        opt_item[i] = true;
                }
                return ;
            }
            else {
                tmp_v += item[tmp_i].v * (capacity - tmp_w) / item[tmp_i].w;
                tmp_w = capacity;
            }
        }
        if (tmp_v <= opt_v) return;

        if (weight + item[idx].w <= capacity) {
            used[idx] = true;
            Rec(idx + 1, value + item[idx].v, weight + item[idx].w);
            used[idx] = false;
        }

        Rec(idx + 1, value, weight);
    }
};
// ------------------------------------------8<------- end of library -------8<----------------------------------------------


int main() {
    cin.tie(0); ios::sync_with_stdio(false);
  int t;
  cin>>t;
  while(t--){
    // AOJ DPL_1_B 問題
    int n;
    ll cap, w, v;

    cin >> n >> cap;
    Knapsack<ll> kp(n, cap);
    ll a=1,b=1,c=2;
    for (int i = 0; i < n; ++i) {
        cin>>w;
        kp.add_item(b, w);
      a=b;
      b=c;
      c=a+b;
    }

    cout << kp.MaximumValue() << endl;
  }

    return 0;
}
0