00001
00002
00003 #ifndef _MKC_KNAPSACK_H
00004 #define _MKC_KNAPSACK_H
00005
00006 #include "BCP_vector.hpp"
00007
00008 class BCP_buffer;
00009
00010
00011
00012
00013 struct MKC_knapsack_entry {
00014 int orig_index;
00015 int index;
00016 int color;
00017 double weight;
00018 double orig_cost;
00019 double cost;
00020 double ratio;
00021 public:
00022 MKC_knapsack_entry() : orig_index(-2), index(-2), color(-2),
00023 weight(0.0), orig_cost(0.0), cost(0.0), ratio(0.0) {}
00024 ~MKC_knapsack_entry() {}
00025 void pack(BCP_buffer& buf);
00026 void unpack(BCP_buffer& buf);
00027 };
00028
00029
00030
00031 inline bool MKC_ks_entry_color_ascend(const MKC_knapsack_entry& order0,
00032 const MKC_knapsack_entry& order1)
00033 {
00034 return order0.color < order1.color;
00035 }
00036
00037 inline bool MKC_ks_entry_ratio_descend(const MKC_knapsack_entry& order0,
00038 const MKC_knapsack_entry& order1)
00039 {
00040 return order0.ratio > order1.ratio;
00041 }
00042
00043 inline bool MKC_ks_entry_weight_ascend(const MKC_knapsack_entry& order0,
00044 const MKC_knapsack_entry& order1)
00045 {
00046 return order0.weight < order1.weight;
00047 }
00048
00049 inline bool MKC_ks_entry_weight_descend(const MKC_knapsack_entry& order0,
00050 const MKC_knapsack_entry& order1)
00051 {
00052 return order0.weight < order1.weight;
00053 }
00054
00055
00056
00057 class MKC_knapsack_fixing {
00058 public:
00059
00060
00061
00062
00063
00064 BCP_vec<char> fixing;
00065 int fixed_entry_num;
00066 int * fixed_entries;
00067 int * fixed_entries_ind;
00068 double fixed_cost;
00069 double fixed_weight;
00070 public:
00071 MKC_knapsack_fixing() :
00072 fixed_entry_num(0), fixed_entries(0), fixed_entries_ind(0),
00073 fixed_cost(0.0), fixed_weight(0.0) {}
00074 ~MKC_knapsack_fixing() {
00075 delete[] fixed_entries_ind;
00076 delete[] fixed_entries;
00077 }
00078 };
00079
00080
00081
00082
00083 class MKC_knapsack {
00084 public:
00085 double cost;
00086 double capacity;
00087 int size;
00088
00089 MKC_knapsack_entry * entries;
00090
00091 int color_num;
00092 int * color_beg;
00093
00094 int orig_index;
00095
00096 public:
00097 MKC_knapsack() :
00098 cost(0.0), capacity(0.0), size(0), entries(0),
00099 color_num(0), color_beg(0), orig_index(-1) {}
00100 ~MKC_knapsack() {
00101 delete[] entries;
00102 delete[] color_beg;
00103 }
00104
00105 void pack(BCP_buffer& buf);
00106 void unpack(BCP_buffer& buf);
00107 };
00108
00109
00110
00111 class MKC_knapsack_set {
00112 public:
00113 int order_num;
00114 int ks_num;
00115 MKC_knapsack* ks_list;
00116 int orig_var_num;
00117 char **orig_name_list;
00118 double * orig_row_0;
00119 double * orig_row_1;
00120 public:
00121 MKC_knapsack_set() :
00122 order_num(0), ks_num(0), ks_list(0),
00123 orig_var_num(0), orig_name_list(0), orig_row_0(0), orig_row_1(0) {}
00124 ~MKC_knapsack_set() {
00125 delete[] ks_list;
00126 if (orig_name_list) {
00127 for (int i = 0; i < orig_var_num; ++i)
00128 delete[] orig_name_list[i];
00129 delete[] orig_name_list;
00130 }
00131 delete[] orig_row_0;
00132 delete[] orig_row_1;
00133 }
00134
00135 void pack(BCP_buffer& buf);
00136 void unpack(BCP_buffer& buf);
00137 };
00138
00139 #endif