From 1ee38d2e0d887507a84e926b1564162fc30776c3 Mon Sep 17 00:00:00 2001 From: APTX Date: Tue, 30 Nov 2010 00:55:15 +0100 Subject: [PATCH] Init --- .gitignore | 75 +++++++ build/zadanie.txt | 23 +++ shared/shared.h | 22 ++ tal-algorithm/main.cpp | 356 ++++++++++++++++++++++++++++++++ tal-algorithm/tal-algorithm.pro | 7 + tal-generator/main.cpp | 79 +++++++ tal-generator/tal-generator.pro | 7 + tal.pro | 5 + 8 files changed, 574 insertions(+) create mode 100644 .gitignore create mode 100644 build/zadanie.txt create mode 100644 shared/shared.h create mode 100644 tal-algorithm/main.cpp create mode 100644 tal-algorithm/tal-algorithm.pro create mode 100644 tal-generator/main.cpp create mode 100644 tal-generator/tal-generator.pro create mode 100644 tal.pro diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..2f8834d --- /dev/null +++ b/.gitignore @@ -0,0 +1,75 @@ +# This file is used to ignore files which are generated +# ---------------------------------------------------------------------------- + +*~ +*.a +*.core +*.moc +*.o +*.obj +*.orig +*.rej +*.so +*_pch.h.cpp +*_resource.rc +*.qm +.#* +*.*# +core +.qmake.cache +tags +.DS_Store +*.debug +Makefile* +*.prl +*.app +moc_*.cpp +ui_*.h +qrc_*.cpp + +# qtcreator generated files +*.pro.user +*.pro.user.* + +# xemacs temporary files +*.flc + +# Vim temporary files +.*.swp + +# Visual Studio generated files +*.ib_pdb_index +*.idb +*.ilk +*.pdb +*.sln +*.suo +*.vcproj +*vcproj.*.*.user +*.ncb +*.exp + +# MinGW generated files +*.Debug +*.Release + +# Directories to ignore +# --------------------- + +debug +release +lib/qtsingleapplication/lib +lib/qtsingleapplication/examples +lib/qtsingleapplication/doc +.tmp +qtc-gdbmacros + +# Binaries +# -------- +build/aniplayer +build/*.dll +build/*.lib +build/*.exe +build/*.so* + + diff --git a/build/zadanie.txt b/build/zadanie.txt new file mode 100644 index 0000000..5195a76 --- /dev/null +++ b/build/zadanie.txt @@ -0,0 +1,23 @@ +400 22 +150 9 +35 13 +200 153 +160 50 +60 15 +45 68 +60 27 +40 39 +30 23 +10 52 +70 11 +30 32 +15 24 +10 48 +40 73 +70 42 +75 43 +80 22 +20 7 +12 18 +50 4 +10 30 diff --git a/shared/shared.h b/shared/shared.h new file mode 100644 index 0000000..f2c7ee1 --- /dev/null +++ b/shared/shared.h @@ -0,0 +1,22 @@ +#include + +bool atoi_wrapper(const char *s, int *result) +{ + const int tmp = atoi(s); + if (tmp < 1 + || tmp == INT_MAX + || tmp == INT_MIN) + return false; + *result = tmp; + return true; +} + +int rand_wrapper(int min, int max) +{ + return min + int((double(rand()) / RAND_MAX) * (max - min)); +} + +inline int max(int a, int b) +{ + return a ^ ((a ^ b) & -(a < b)); +} diff --git a/tal-algorithm/main.cpp b/tal-algorithm/main.cpp new file mode 100644 index 0000000..f0a6a1f --- /dev/null +++ b/tal-algorithm/main.cpp @@ -0,0 +1,356 @@ +#include +#include +#include +#include +#include "../shared/shared.h" + +using namespace std; + +// =============================================================================== +// Problem structure +// =============================================================================== + +struct Item +{ + int value; + int weight; + bool solution; +}; + +struct Problem +{ + int limit; + int count; + Item *items; + + bool solved; + int totalWeight; + int totalValue; + + Problem() + { + items = 0; + limit = 0; + count = 0; + solved = false; + totalWeight = 0; + totalValue = 0; + } + + ~Problem() + { + if (items) + delete[] items; + } +}; + +// =============================================================================== +// DP Algorithm +// =============================================================================== + + +class Array2d +{ + friend ostream &operator<<(ostream &o, const Array2d &p); + int *a; + int w; + int h; + +public: + Array2d(int w, int h) + { + a = new int[w * h]; + memset(a, 0, h * sizeof(int)); + this->w = w; + this->h = h; + } + + ~Array2d() + { + delete[] a; + } + + inline int &operator()(int x, int y) + { + return a[y + x * h]; + } + + inline const int &operator()(int x, int y) const + { + return a[y + x * h]; + } +}; + +ostream &operator<<(ostream &o, const Array2d &p) +{ + o << "W="< p.h - 1) + { + t = 0; + o << endl; + } + } + return o; +} + +ostream &operator<<(ostream &o, const Problem &p) +{ + o << "Limit: " << p.limit << "\nItems:\n"; + + int numw = int(log10(double(p.count))) + 1; + + int vw = 0; + int ww = 0; + int rw = 0; + + for (int i = 0; i < p.count; ++i) + { + vw = max(vw, p.items[i].weight); + ww = max(ww, p.items[i].value); + rw = max(rw, int(double(p.items[i].value) / p.items[i].weight)); + } + + vw = int(log10(double(vw))) + 1; + ww = int(log10(double(ww))) + 1; + rw = int(log10(double(rw))) + 1; + + int sum = 0; + for (int i = 0; i < p.count; ++i) + { + o << setfill(' ') << setw(numw) << (i+1) + << ". V = " << setw(vw) << p.items[i].value + << " W = " << setw(ww) << p.items[i].weight + << " R = " << setw(rw + 5) << setprecision(4) << fixed << (double(p.items[i].value) / p.items[i].weight); + if (p.solved && p.items[i].solution) + { + o << " Part of solution!"; + sum += p.items[i].value; + } + o << endl; + } + if (p.solved) + { + o << "Total: " << sum << endl; + } + return o; +} + +void solve_dp(Problem * p) +{ + Array2d V(p->count + 1, p->limit + 1); + +/* + // Initialized in Array2d constructor + for (int w = 0; w <= p->limit; ++w) + { + V(0, w) = 0; + } +*/ + for (int k = 0; k < p->count; ++k) + { + V(k + 1, 0) = 0; + for (int w = 1; w <= p->limit; ++w) + { + if (p->items[k].weight > w) + V(k + 1, w) = V(k, w); + else + V(k + 1, w) = max(V(k, w), p->items[k].value + V(k, w - p->items[k].weight)); + } + } + + int w = p->limit; + int totalWeight = 0; + for (int i = p->count; i > 0; --i) + { + if (V(i, w) == V(i - 1, w)) + { + p->items[i - 1].solution = false; + } + else + { + p->items[i - 1].solution = true; + w -= p->items[i - 1].weight; + totalWeight += p->items[i - 1].weight; + } + } + p->solved = true; + p->totalValue = V(p->count, p->limit); + p->totalWeight = totalWeight; +} + +// =============================================================================== +// Greedy Algorithm +// =============================================================================== + +bool greed_HighestValue(const Item &a, const Item &b) +{ + return a.value > b.value; +} + +bool greed_LowestWeight(const Item &a, const Item &b) +{ + return a.weight < b.weight; +} + +bool greed_BestRatio(const Item &a, const Item &b) +{ + return double(a.value / a.weight) > double(b.value / b.weight); +} + +void solve_greedy(Problem *p, bool (*greed_func)(const Item &a, const Item &b)) +{ + sort(p->items, p->items + p->count, greed_func); + + + int totalWeight = 0; + int totalValue = 0; + + for (int i = 0; i < p->count; ++i) + { + if (p->items[i].weight + totalWeight <= p->limit) + { + totalWeight += p->items[i].weight; + totalValue += p->items[i].value; + p->items[i].solution = true; + } + else + { + p->items[i].solution = false; + } + } + p->solved = true; + p->totalWeight = totalWeight; + p->totalValue = totalValue; +} + +// =============================================================================== +// Misc +// =============================================================================== + +Problem *read_problem(istream &input, bool *success) +{ + Problem *p = new Problem; + + *success = false; + + if (input.rdstate() & ios_base::failbit) + { + cout << "empty" << endl; + } + + input >> p->limit; + if (cin.rdstate() & ios_base::failbit) goto error; + + + input >> p->count; + if (cin.rdstate() & ios_base::failbit) goto error; + + p->items = new Item[p->count]; + + for (int i = 0; i < p->count; ++i) + { + input >> p->items[i].value; + if (cin.rdstate() & ios_base::failbit) goto error; + + input >> p->items[i].weight; + if (cin.rdstate() & ios_base::failbit) goto error; + + } + + *success = true; +error: + return p; +} + +int main(int argc, char **argv) +{ + + bool run_dp = false; + bool run_greedy_HighestValue = false; + bool run_greedy_LowestWeight = false; + bool run_greedy_BestRatio = false; + int runs = 1; + + if (argc < 2) + goto help; + + for (int i = 1; i < argc; ++i) + { + if (!strcmp(argv[i], "-h") + || !strcmp(argv[i], "-help")) + { + goto help; + } + + else if (!strcmp(argv[i], "-r")) + { + if (++i == argc) goto help; + if(!atoi_wrapper(argv[i], &runs)) goto help; + runs = max(1, runs); + } + else if (!strcmp(argv[i], "-dp")) + { + run_dp = true; + } + else if (!strcmp(argv[i], "-gv")) + { + run_greedy_HighestValue = true; + } + else if (!strcmp(argv[i], "-gw")) + { + run_greedy_LowestWeight = true; + } + else if (!strcmp(argv[i], "-gr")) + { + run_greedy_BestRatio = true; + } + } + + bool success; + Problem *p = read_problem(cin, &success); + + if (!success) + { + delete p; + goto help; + } +cout << *p; + for (int i = 0; i < runs; ++i) + { + if (run_dp) + { + solve_dp(p); + cout << "dp\t" << p->totalValue << "\t" << p->totalWeight << endl; + } + if (run_greedy_HighestValue) + { + solve_greedy(p, greed_HighestValue); + cout << "gv\t" << p->totalValue << "\t" << p->totalWeight << endl; + } + if (run_greedy_LowestWeight) + { + solve_greedy(p, greed_LowestWeight); + cout << "gw\t" << p->totalValue << "\t" << p->totalWeight << endl; + } + if (run_greedy_BestRatio) + { + solve_greedy(p, greed_BestRatio); + cout << "gr\t" << p->totalValue << "\t" << p->totalWeight << endl; + } + } + + delete p; + return 0; +help: + printf( + "-r\t\tNumber of runs. Must be at least 1\n" + "-dp\t<>\tRun Dynamic Programming Algorithm.\n" + "-gv\t<>\tRun Greedy Algorithm for highest value.\n" + "-gw\t<>\tRun Greedy Algorithm for lowest weight.\n" + "-dr\t<>\tRun Greedy Algorithm for highest value-to-weight ratio.\n" + , runs); + return 1; +} diff --git a/tal-algorithm/tal-algorithm.pro b/tal-algorithm/tal-algorithm.pro new file mode 100644 index 0000000..405bb61 --- /dev/null +++ b/tal-algorithm/tal-algorithm.pro @@ -0,0 +1,7 @@ +QT -= core gui +CONFIG += console +DESTDIR = ../build +SOURCES += \ + main.cpp +HEADERS += \ + ../shared/shared.h diff --git a/tal-generator/main.cpp b/tal-generator/main.cpp new file mode 100644 index 0000000..2b24bda --- /dev/null +++ b/tal-generator/main.cpp @@ -0,0 +1,79 @@ +#include +#include +#include +#include "../shared/shared.h" + +int main(int argc, char **argv) +{ + int l = 2000; + int n = 5; + int vmin = 1; + int vmax = 1000; + int wmin = 1; + int wmax = 1000; + + for (int i = 1; i < argc; ++i) + { + if (!strcmp(argv[i], "-h") + || !strcmp(argv[i], "-help")) + { + goto help; + } + + else if (!strcmp(argv[i], "-l")) + { + if (++i == argc) goto help; + if(!atoi_wrapper(argv[i], &l)) goto help; + } + else if (!strcmp(argv[i], "-n")) + { + if (++i == argc) goto help; + if(!atoi_wrapper(argv[i], &n)) goto help; + } + else if (!strcmp(argv[i], "-vmin")) + { + if (++i == argc) goto help; + if(!atoi_wrapper(argv[i], &vmin)) goto help; + } + else if (!strcmp(argv[i], "-vmax")) + { + if (++i == argc) goto help; + if(!atoi_wrapper(argv[i], &vmax)) goto help; + } + else if (!strcmp(argv[i], "-wmin")) + { + if (++i == argc) goto help; + if(!atoi_wrapper(argv[i], &wmin)) goto help; + } + else if (!strcmp(argv[i], "-wmax")) + { + if (++i == argc) goto help; + if(!atoi_wrapper(argv[i], &wmax)) goto help; + } + } + + if (vmax < vmin || wmax < wmin) + goto help; + + srand(int(time(NULL))); + + printf("%d %d\n", l, n); + for (int i = 0; i < n; ++i) + { + printf("%d %d\n", rand_wrapper(vmin, vmax), rand_wrapper(wmin, wmax)); + } + + return 0; +help: + printf("USAGE: %s \n\n" + "ARGS are:\n" + "-l\t\tWeight limit.\n" + "-n\t\tNumber of items.\n" + "-vmin\t\tMinimum value.\n" + "-vmax\t\tMaximum value. Cannot be less than minimum.\n" + "-wmin\t\tMinimum weight.\n" + "-wmax\t\tMaximum weight. Cannot be less than minimum.\n" + "-h -help Print this message.\n" + , argv[0], l, n, vmin, vmax, wmin, wmax); + return 1; +} diff --git a/tal-generator/tal-generator.pro b/tal-generator/tal-generator.pro new file mode 100644 index 0000000..405bb61 --- /dev/null +++ b/tal-generator/tal-generator.pro @@ -0,0 +1,7 @@ +QT -= core gui +CONFIG += console +DESTDIR = ../build +SOURCES += \ + main.cpp +HEADERS += \ + ../shared/shared.h diff --git a/tal.pro b/tal.pro new file mode 100644 index 0000000..8b2d706 --- /dev/null +++ b/tal.pro @@ -0,0 +1,5 @@ +CONFIG += ordered +TEMPLATE = subdirs + +SUBDIRS += tal-generator \ + tal-algorithm -- 2.52.0