#826872 (C++17) No.2167 Fibonacci Knapsack

• 問題: 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

ソースコード

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX