//http://zeus.mech.kyushu-u.ac.jp/~tsuji/java_edu/Simplex_st.htmlを参考に実装. //整数計画じゃないから最適より大きい値が出る可能性、普通にあるのよねぇ… #include #include #include #include #include //表示用関数で使っている #define rep(i, n) for(i = 0; i < n; i++) using namespace std; typedef vector Vector; typedef vector Mat; //a >= 0 string toString(int a) { if (a == 0) return "0"; string s; while (a > 0) { s += (char)((a % 10) + '0'); a /= 10; } int l = 0, r = s.length() - 1; while (l < r) { char c = s[l]; s[l] = s[r]; s[r] = c; l++; r--; } return s; } //表示用. とりあえず整数部分は全て変換. 小数点以下はketa桁まで変換. 基本, 切捨て. //・-2.775が"-2.774"に変換されたり、0.53が"0.530"に変換されてしまう不具合。浮動小数点数誤差っぽい。 //・微小値epsを用意して、a < 0ならepsを引いておき、a > 0ならepsを足しておく。 //・"0.530"のようになったら、小数部の末尾の0を消す. 全部消えたら小数点も消す. string toString(double a, int keta) { bool minus_flag = false; //ここ、aが大きいほど足し引きする微小量も大きくした方がいいんだけど、面倒くさいからこうしている。 if (a >= 0) { a += 1e-12; } else { minus_flag = true; a -= 1e-12; } int ia = a; //example. a = -2.5 -> ia = -2. a = 2.5 -> ia = 2. a = 0.1 -> ia = 0. string istr; if (minus_flag) istr += "-"; istr += toString(ia * ((ia < 0) ? -1 : 1)); double da = a - ia; if (da < 0) da = -da; string dstr; int i; for (i = 0; i < keta; i++) { da *= 10; int val = (int)da; dstr += (char)('0' + val); da -= val; } for (i = (int)dstr.length() - 1; i >= 0; i--) { if (dstr[i] != '0') { break; } } int lim_i = i; string dStr; for (i = 0; i <= lim_i; i++) { dStr += dstr[i]; } if (dStr.length() == 0) return istr; return istr + "." + dStr; } //手抜き実装なので、10変数以上あると表示が崩れます. void print_simplex_state(vector &ids, Mat &table, Vector &con) { int i, j; vector max_length(table[0].size(), 0); rep(i, table.size()) { rep(j, table[i].size()) { max_length[j] = toString(table[i][j], 6).length(); } } rep(j, table[0].size()) { int length = 2 + toString(i).length(); if (max_length[j] < length) max_length[j] = length; } cout << "基底変数 | "; rep(i, table[0].size()) { string str = toString(i); for (j = 0; j + str.length() + 2 < max_length[i]; j++) { cout << " "; } cout << "x_" << str << ", "; } cout << "定数項" << endl; rep(i, table.size()) { if (ids[i] == -1) cout << "z | "; else { string str = toString(ids[i]); cout << "x_" << str; for (j = 2 + str.length(); j < 9; j++) cout << " "; cout << "| "; } rep(j, table[i].size()) { string str = toString(table[i][j], 6); for (int k = 0; k + str.length() < max_length[j]; k++) cout << " "; cout << table[i][j] << ", "; } cout << con[i] << endl; } cout << endl; } //max. cx, s.t Ax <= bを解く. xはベクトル. x = 0は条件を満たすと仮定する. //[非基底変数;最大化したい式に含まれる変数. 制約の範囲で自由に動かす. 各ステップ開始時に値が0になっている。] tuple> simplex_leq(Mat A, Vector b, Vector c) { tuple> error_value = tuple>(false, 0, vector()); vector ids; //ids[i] = i(>=0)行目の基底変数はx[ids[i]]. 0行目は目的変数Zなので, ids[0] = -1とする. Mat table; //table : シンプレックス表, table[i] = i=0:目的変数Zの制約式, i>=1:制約式 //table[i][j] = i個目の制約式(等式の左辺)における、変数x[j]の係数. Vector con; //con[i] = i個目の制約式の定数項. i=0のときは目的変数Zの制約式の定数項 (現在の値). //理論上, x = 0が条件を満たす場合, con[i] >= 0は常に満たされる. int w = c.size() + A.size(); //変数x[0]~x[c.size()-1] + スラック変数:x[c.size()]~, 全て非負 int h = 1 + A.size(); //目的関数がある分、制約式 + 1行にしておく。 int i, j; ids.resize(h); ids[0] = -1; rep(i, A.size()) ids[i + 1] = c.size() + i; //最初は, スラック変数が基底変数 table.resize(h); rep(i, h) table[i].resize(w); rep(j, w) { if (j < c.size()) table[0][j] = -c[j]; else table[0][j] = 0; } rep(i, A.size()) { rep(j, w) { if (j < A[i].size()) table[i + 1][j] = A[i][j]; else if (j == A[i].size() + i) table[i + 1][j] = 1; else table[i + 1][j] = 0; } } con.resize(h + 1); con[0] = 0; rep(i, b.size()) con[i + 1] = b[i]; //では解いていきましょう while (true) { //print_simplex_state(ids, table, con); //STEP1. table[0] (目的関数の係数) の中から最小な係数がある列qを求める int q = 0; rep(j, w) { if (table[0][q] > table[0][j]) { q = j; } } //STEP2. table[0]の係数が全て非負になったら終了. 目的関数の値はこれ以上増加しないため. if (table[0][q] >= 0) { break; } //STEP3. table[i][q] > 0になる行i=1,2,…,h-1の中から、 //con[i] / table[i][q]が最小となる行pを探す. (変数x[q]をいくつ増やせるか) //そのようなpが存在しなければ、最適値が存在しない(いくらでも大きくできてしまう) int p = -1; double min_t; for (i = 1; i < h; i++) { if (table[i][q] <= 0) continue; double t = con[i] / table[i][q]; if (p == -1 || min_t > t) { min_t = t; p = i; } } if (p == -1) { return error_value; } //STEP4. p行q列をピポットにして掃き出し法をおこなう. //基底変数の交換 -> 代入に相当する操作. double c0 = table[p][q]; rep(j, w) table[p][j] /= c0; con[p] /= c0; rep(i, h) { if (i == p) continue; double c1 = -table[i][q]; rep(j, w) { table[i][j] += c1 * table[p][j]; } con[i] += c1 * con[p]; } ids[p] = q; } //解を返す double max_z = con[0]; vector x(c.size(), 0); for (i = 1; i < h; i++) { if (0 <= ids[i] && ids[i] < c.size()) { x[ids[i]] = con[i]; } } return tuple>(true, max_z, x); } int main() { int i, j; int a[5]; cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4]; Vector c, b; Mat A; c.resize(5); rep(i, 5) c[i] = 1; A.resize(5); b.resize(5); rep(i, 5) { A[i].resize(5); rep(j, 3) { A[i][(i + j) % 5] = 1; } A[i][(i + 3) % 5] = 0; A[i][(i + 4) % 5] = 0; b[i] = a[(i + 2) % 5]; } tuple> ans = simplex_leq(A, b, c); bool isSucceed = get<0>(ans); double max_z = get<1>(ans); vector x = get<2>(ans); if (isSucceed) { cout << (long long)(max_z + 1e-9) << endl; /*cout << "z = " << max_z << endl; rep(i, x.size()) { cout << "x_" << i << " = " << x[i] << endl; }*/ } else { assert(0); //cout << "Fail" << endl; } return 0; }