Week_4_Task_2

int: n = 50;

array[1..n] of int: weight = [91, 24, 13, 45, 41, 38, 27, 23, 96, 79, 21, 85, 64, 14, 13, 21, 37, 39, 74, 87, 13, 81, 35, 93, 99, 79, 63, 38, 67, 85, 45, 10, 30, 99, 64, 53, 45, 29, 37, 53, 23, 21, 58, 22, 55, 54, 87, 43, 15, 68];

array[1..n] of int: value = [51, 116, 40, 95, 112, 69, 37, 31, 78, 94, 40, 79, 45, 117, 91, 136, 113, 61, 114, 110, 73, 88, 38, 63, 82, 61, 138, 117, 89, 76, 103, 34, 78, 28, 100, 122, 88, 36, 74, 100, 74, 147, 121, 137, 56, 87, 55, 83, 87, 129];

int: capacity = 832;

set of int: ITEMS = 1..n;

array[ITEMS] of var 0..1: used;

array [ITEMS] of float: denisty = [value[i] / weight[i] | i in ITEMS];

var int: total_value = sum(i in ITEMS)(value[i] * used[i]);
var int: total_weight = sum(i in ITEMS)(weight[i] * used[i]);

set of int: feasible = { i | i in ITEMS where weight[i] <= capacity };
int: max_feasible_value = max([ value[i] | i in feasible ]);
constraint total_value >= max_feasible_value;

constraint sum(i in ITEMS)(used[i]) <= 30; %В лучшем ответе было < 30, поэтому я выбрал 30.

constraint sum(i in ITEMS)(weight[i] * used[i]) <= capacity;

array[ITEMS] of int: density_order = arg_sort([-denisty[i] | i in ITEMS]);

solve :: int_search([used[i] | i in density_order], first_fail, indomain_max) maximize total_value;

output [
"=== Решение задачи о рюкзаке ===\n",
"Выбранные предметы:\n"
] ++
[
  if fix(used[i]) = 1 then
    " Предмет \(i): вес=\(weight[i]), ценность=\(value[i]), плотность ценности=\(denisty[i])\n"
  else "" endif
  | i in ITEMS
] ++
[
"Итого: вес=\(total_weight), ценность=\(total_value)\n"
];

/*
=== Решение задачи о рюкзаке ===
Выбранные предметы:
 Предмет 2: вес=24, ценность=116, плотность ценности=4.833333333333333
 Предмет 3: вес=13, ценность=40, плотность ценности=3.076923076923077
 Предмет 4: вес=45, ценность=95, плотность ценности=2.111111111111111
 Предмет 5: вес=41, ценность=112, плотность ценности=2.731707317073171
 Предмет 6: вес=38, ценность=69, плотность ценности=1.815789473684211
 Предмет 14: вес=14, ценность=117, плотность ценности=8.357142857142858
 Предмет 15: вес=13, ценность=91, плотность ценности=7.0
 Предмет 16: вес=21, ценность=136, плотность ценности=6.476190476190476
 Предмет 17: вес=37, ценность=113, плотность ценности=3.054054054054054
 Предмет 21: вес=13, ценность=73, плотность ценности=5.615384615384615
 Предмет 27: вес=63, ценность=138, плотность ценности=2.190476190476191
 Предмет 28: вес=38, ценность=117, плотность ценности=3.078947368421053
 Предмет 31: вес=45, ценность=103, плотность ценности=2.288888888888889
 Предмет 32: вес=10, ценность=34, плотность ценности=3.4
 Предмет 33: вес=30, ценность=78, плотность ценности=2.6
 Предмет 36: вес=53, ценность=122, плотность ценности=2.30188679245283
 Предмет 37: вес=45, ценность=88, плотность ценности=1.955555555555555
 Предмет 39: вес=37, ценность=74, плотность ценности=2.0
 Предмет 41: вес=23, ценность=74, плотность ценности=3.217391304347826
 Предмет 42: вес=21, ценность=147, плотность ценности=7.0
 Предмет 43: вес=58, ценность=121, плотность ценности=2.086206896551724
 Предмет 44: вес=22, ценность=137, плотность ценности=6.227272727272728
 Предмет 48: вес=43, ценность=83, плотность ценности=1.930232558139535
 Предмет 49: вес=15, ценность=87, плотность ценности=5.8
 Предмет 50: вес=68, ценность=129, плотность ценности=1.897058823529412
Итого: вес=830, ценность=2494
*/