Yamari/Knapsack
0
1from typing import List, Tuple2from ortools.sat.python import cp_model3 4from shapes import ROWS, COLS, ORIENTATION_BY_ID5 6 7def cell_to_bit(r, c):8 return 1 << (r * COLS + c)9 10def bit_to_cell(bit):11 """Обратное преобразование: бит -> (r,c)"""12 idx = bit.bit_length() - 113 return divmod(idx, COLS)14 15# ------------------------------------------------------------16# OR-TOOLS СОЛВЕР17# ------------------------------------------------------------18class Solver:19 def __init__(self, items: List[dict]):20 """21 items: список словарей с ключами 'orientation_id', 'value'22 """23 self.items = items24 self.n = len(items)25 self.model = cp_model.CpModel()26 self.solver = cp_model.CpSolver()27 self.placements = [[] for _ in range(self.n)]28 self._generate_placements()29 30 def _generate_placements(self):31 for idx, it in enumerate(self.items):32 orient = ORIENTATION_BY_ID[it['orientation_id']]33 coords = orient['coords']34 for r0 in range(ROWS):35 for c0 in range(COLS):36 mask = 037 ok = True38 for dy, dx in coords:39 r, c = r0 + dy, c0 + dx40 if r >= ROWS or c >= COLS:41 ok = False42 break43 mask |= cell_to_bit(r, c)44 if ok:45 self.placements[idx].append((mask, it['value']))46 # Убираем дубликаты масок47 unique = {}48 for mask, val in self.placements[idx]:49 unique[mask] = val50 self.placements[idx] = [(m, v) for m, v in unique.items()]51 52 def solve(self, time_limit_seconds=5.0) -> Tuple[int, List[Tuple[int, int]]]:53 if self.n == 0:54 return 0, []55 56 placement_vars = []57 for idx in range(self.n):58 pvars = []59 for pidx, (mask, val) in enumerate(self.placements[idx]):60 var = self.model.NewBoolVar(f'p_{idx}_{pidx}')61 pvars.append((var, mask, val))62 placement_vars.append(pvars)63 64 # Каждый предмет используется не более одного раза65 for idx in range(self.n):66 self.model.Add(sum(var for var, _, _ in placement_vars[idx]) <= 1)67 68 # Каждая клетка занята не более одного раза69 for r in range(ROWS):70 for c in range(COLS):71 cell_bit = cell_to_bit(r, c)72 cell_vars = []73 for idx in range(self.n):74 for var, mask, _ in placement_vars[idx]:75 if mask & cell_bit:76 cell_vars.append(var)77 if cell_vars:78 self.model.Add(sum(cell_vars) <= 1)79 80 # Целевая функция81 objective = []82 for idx in range(self.n):83 for var, _, val in placement_vars[idx]:84 objective.append(var * val)85 self.model.Maximize(sum(objective))86 87 self.solver.parameters.max_time_in_seconds = time_limit_seconds88 status = self.solver.Solve(self.model)89 90 if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:91 taken = []92 total = 093 for idx in range(self.n):94 for pidx, (var, mask, val) in enumerate(placement_vars[idx]):95 if self.solver.Value(var):96 taken.append((idx, mask))97 total += val98 break99 return total, taken100 return 0, []101 102 103class PolyominoSolverWithBonus:104 """105 Солвер для упаковки полимино с бонусами за соседство специальных предметов одного типа.106 """107 def __init__(self, items, bonus_per_adjacent=100):108 """109 items : list of dict110 Каждый словарь содержит:111 - orientation_id (int)112 - value (int) – базовая стоимость113 - type_id (int) – тип предмета114 - special (bool) – True, если предмет получает бонус за соседство115 bonus_per_adjacent : float/int116 Бонус за каждую общую грань между двумя подходящими предметами117 """118 self.items = items119 self.bonus = bonus_per_adjacent120 self.n = len(items)121 self.model = cp_model.CpModel()122 self.solver = cp_model.CpSolver()123 self.placements = [] # для каждого предмета список (mask, value)124 self.x_vars = [] # переменные выбора позиций125 self.bonus_vars = [] # список (y_var, coefficient)126 self._generate_placements()127 self._build_model()128 129 def _generate_placements(self):130 """Генерирует все допустимые позиции для каждого предмета (как в базовом солвере)"""131 self.placements = [[] for _ in range(self.n)]132 for idx, it in enumerate(self.items):133 orient = ORIENTATION_BY_ID[it["orientation_id"]]134 coords = orient["coords"]135 for r0 in range(ROWS):136 for c0 in range(COLS):137 mask = 0138 ok = True139 for dy, dx in coords:140 r, c = r0 + dy, c0 + dx141 if r >= ROWS or c >= COLS:142 ok = False143 break144 mask |= cell_to_bit(r, c)145 if ok:146 self.placements[idx].append((mask, it["value"]))147 # удаляем дубликаты масок148 unique = {}149 for mask, val in self.placements[idx]:150 unique[mask] = val151 self.placements[idx] = [(m, v) for m, v in unique.items()]152 153 @staticmethod154 def _count_adjacent(mask1, mask2):155 """Возвращает количество общих граней между двумя масками."""156 adj = 0157 for r in range(ROWS):158 for c in range(COLS):159 if mask1 & cell_to_bit(r, c):160 # проверяем четырёх соседей161 for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:162 nr, nc = r+dr, c+dc163 if 0 <= nr < ROWS and 0 <= nc < COLS:164 if mask2 & cell_to_bit(nr, nc):165 adj += 1166 return adj167 168 def _build_model(self):169 # 1. Переменные выбора позиций170 for idx in range(self.n):171 pvars = []172 for pidx, (mask, val) in enumerate(self.placements[idx]):173 var = self.model.NewBoolVar(f'x_{idx}_{pidx}')174 pvars.append((var, mask, val))175 self.x_vars.append(pvars)176 # предмет можно разместить не более одного раза177 self.model.Add(sum(v for v, _, _ in pvars) <= 1)178 179 # 2. Ограничения по клеткам (каждая клетка занята не более одного раза)180 for r in range(ROWS):181 for c in range(COLS):182 cell_bit = cell_to_bit(r, c)183 cell_vars = []184 for idx in range(self.n):185 for var, mask, _ in self.x_vars[idx]:186 if mask & cell_bit:187 cell_vars.append(var)188 if cell_vars:189 self.model.Add(sum(cell_vars) <= 1)190 191 # 3. Бонусные переменные для пар предметов192 for i in range(self.n):193 for j in range(i+1, self.n):194 # проверяем, что оба special и одного типа195 if not (self.items[i]['special'] and self.items[j]['special'] and196 self.items[i]['type_id'] == self.items[j]['type_id']):197 continue198 # перебираем все пары позиций199 for pi, (var_i, mask_i, _) in enumerate(self.x_vars[i]):200 for pj, (var_j, mask_j, _) in enumerate(self.x_vars[j]):201 if mask_i & mask_j: # пересекаются – не могут быть вместе202 continue203 adj = self._count_adjacent(mask_i, mask_j)204 if adj > 0:205 y = self.model.NewBoolVar(f'y_{i}_{pi}_{j}_{pj}')206 # y <= x_i, y <= x_j207 self.model.Add(y <= var_i)208 self.model.Add(y <= var_j)209 # y >= x_i + x_j - 1210 self.model.Add(y >= var_i + var_j - 1)211 self.bonus_vars.append((y, adj * self.bonus))212 213 # 4. Целевая функция214 objective_terms = []215 for idx in range(self.n):216 for var, _, val in self.x_vars[idx]:217 objective_terms.append(var * val)218 for y, coeff in self.bonus_vars:219 objective_terms.append(y * coeff)220 self.model.Maximize(sum(objective_terms))221 222 def solve(self, time_limit_seconds=5.0):223 self.solver.parameters.max_time_in_seconds = time_limit_seconds224 status = self.solver.Solve(self.model)225 226 taken = []227 total_value = 0228 for idx in range(self.n):229 for pidx, (var, mask, val) in enumerate(self.x_vars[idx]):230 if self.solver.Value(var):231 taken.append((idx, mask))232 total_value += val233 break234 235 # добавляем бонусы (они уже учтены в objective, но для отчёта пересчитаем)236 bonus_total = 0237 for y, coeff in self.bonus_vars:238 if self.solver.Value(y):239 bonus_total += coeff240 total_value += bonus_total # можно не добавлять, если брать objective напрямую241 242 stats = {243 'status': status,244 'status_name': self.solver.StatusName(status),245 'objective': self.solver.ObjectiveValue(),246 'wall_time': self.solver.WallTime(),247 }248 return total_value, taken, stats249 250###------------------------------------------ Z ----------------------------------------------------------------251 252from ortools.sat.python import cp_model253 254# Константы (предполагаем глобальное определение)255# ROWS, COLS, cell_to_bit, ORIENTATION_BY_ID256 257class PolyominoSolverWithBonusZ3:258 def __init__(self, items, size_bonuses=None, time_limit=10.0):259 self.items = items260 self.n = len(items)261 self.size_bonuses = size_bonuses if size_bonuses is not None else {1: 20, 2: 50}262 self.time_limit = time_limit263 264 self.model = cp_model.CpModel()265 self.solver = cp_model.CpSolver()266 267 # --- Настройка солвера для производительности ---268 # 1. Используем все ядра процессора269 self.solver.parameters.num_search_workers = 8 270 # 2. Увеличиваем время (можно передавать параметром)271 self.solver.parameters.max_time_in_seconds = self.time_limit272 # 3. Оставляем поиск внутри ограничений при нахождении решения (важно для knapsack)273 self.solver.parameters.search_branching = cp_model.PORTFOLIO_SEARCH274 275 self.placements = []276 self.x_vars = []277 self.bonus_vars = []278 279 self.item_sizes = []280 for it in self.items:281 orient = ORIENTATION_BY_ID[it["orientation_id"]]282 self.item_sizes.append(len(orient["coords"]))283 284 self._generate_placements()285 self._build_model()286 287 def _generate_placements(self):288 """Генерация позиций (без изменений)"""289 self.placements = [[] for _ in range(self.n)]290 for idx, it in enumerate(self.items):291 orient = ORIENTATION_BY_ID[it["orientation_id"]]292 coords = orient["coords"]293 for r0 in range(ROWS):294 for c0 in range(COLS):295 mask = 0296 ok = True297 for dy, dx in coords:298 r, c = r0 + dy, c0 + dx299 if r >= ROWS or c >= COLS:300 ok = False301 break302 mask |= cell_to_bit(r, c)303 if ok:304 self.placements[idx].append((mask, it["value"]))305 unique = {}306 for mask, val in self.placements[idx]:307 unique[mask] = val308 self.placements[idx] = [(m, v) for m, v in unique.items()]309 310 @staticmethod311 def _count_adjacent_fast(mask1, mask2):312 """313 Быстрый подсчет общих граней через битовые операции.314 Вместо циклов по клеткам используем сдвиги масок.315 """316 # Сдвигаем mask2 во всех 4 направлениях и ищем пересечение с mask1317 # Грань справа: ячейка mask1 касается ячейки mask2 слева (mask2 сдвинута вправо)318 # Внимание: сдвиг вправо (>>) соответствует уменьшению индекса бита,319 # что обычно соответствует движению влево на сетке, если биты нумеруются 0..N слева направо.320 # Главное - мы проверяем все 4 направления.321 322 adj = 0323 # Проверяем касание: ячейка из mask1 и ячейка из mask2 рядом324 # 1. mask2 сдвигаем влево (она становится "левее"), ищем пересечение с mask1 (которая "справа")325 adj += (mask1 & (mask2 << 1)).bit_count()326 # 2. mask2 сдвигаем вправо (она "правее")327 adj += (mask1 & (mask2 >> 1)).bit_count()328 # 3. mask2 сдвигаем вверх (индекс бита уменьшается на ширину строки)329 adj += (mask1 & (mask2 << COLS)).bit_count()330 # 4. mask2 сдвигаем вниз331 adj += (mask1 & (mask2 >> COLS)).bit_count()332 333 return adj334 335 def _items_are_identical(self, i, j):336 """Проверка, являются ли предметы i и j полностью идентичными"""337 item_i = self.items[i]338 item_j = self.items[j]339 return (item_i['orientation_id'] == item_j['orientation_id'] and340 item_i['value'] == item_j['value'] and341 item_i['type_id'] == item_j['type_id'] and342 item_i['special'] == item_j['special'])343 344 def _build_model(self):345 # 1. Переменные выбора позиций346 for idx in range(self.n):347 pvars = []348 for pidx, (mask, val) in enumerate(self.placements[idx]):349 var = self.model.NewBoolVar(f'x_{idx}_{pidx}')350 pvars.append((var, mask, val))351 self.x_vars.append(pvars)352 # Предмет размещается не более одного раза353 self.model.Add(sum(v for v, _, _ in pvars) <= 1)354 355 # --- Разрыв симметрии (Symmetry Breaking) ---356 # Если предметы i и j идентичны, заставляем солвер рассматривать их по порядку.357 # Если j-й предмет размещен, то i-й тоже должен быть рассмотрен (либо размещен, либо нет, 358 # но приоритет размещения у i выше). Строгое правило: 359 # sum(x_i) >= sum(x_j). Это предотвращает перестановки одинаковых предметов.360 for i in range(self.n):361 for j in range(i + 1, self.n):362 if self._items_are_identical(i, j):363 sum_i = sum(v for v, _, _ in self.x_vars[i])364 sum_j = sum(v for v, _, _ in self.x_vars[j])365 self.model.Add(sum_i >= sum_j)366 367 # 2. Ограничения по клеткам368 for r in range(ROWS):369 for c in range(COLS):370 cell_bit = cell_to_bit(r, c)371 cell_vars = []372 for idx in range(self.n):373 for var, mask, _ in self.x_vars[idx]:374 if mask & cell_bit:375 cell_vars.append(var)376 if cell_vars:377 self.model.Add(sum(cell_vars) <= 1)378 379 # 3. Бонусы380 for i in range(self.n):381 for j in range(i+1, self.n):382 if self.items[i]['type_id'] != self.items[j]['type_id']:383 continue384 385 i_spec = self.items[i]['special']386 j_spec = self.items[j]['special']387 if not (i_spec or j_spec):388 continue389 390 size_i = self.item_sizes[i]391 size_j = self.item_sizes[j]392 bonus_i = self.size_bonuses.get(size_i, 0) if i_spec else 0393 bonus_j = self.size_bonuses.get(size_j, 0) if j_spec else 0394 395 pair_bonus_coeff = bonus_i + bonus_j396 if pair_bonus_coeff == 0:397 continue398 399 # Используем быстрый перебор400 for pi, (var_i, mask_i, _) in enumerate(self.x_vars[i]):401 for pj, (var_j, mask_j, _) in enumerate(self.x_vars[j]):402 if mask_i & mask_j:403 continue404 405 # Используем быстрый подсчет406 adj = self._count_adjacent_fast(mask_i, mask_j)407 if adj > 0:408 y = self.model.NewBoolVar(f'y_{i}_{pi}_{j}_{pj}')409 self.model.Add(y <= var_i)410 self.model.Add(y <= var_j)411 self.model.Add(y >= var_i + var_j - 1)412 self.bonus_vars.append((y, pair_bonus_coeff))413 414 # 4. Целевая функция415 objective_terms = []416 for idx in range(self.n):417 for var, _, val in self.x_vars[idx]:418 objective_terms.append(var * val)419 for y, coeff in self.bonus_vars:420 objective_terms.append(y * coeff)421 self.model.Maximize(sum(objective_terms))422 423 def solve(self):424 # Запускаем решение425 status = self.solver.Solve(self.model)426 427 taken = []428 total_value = 0429 for idx in range(self.n):430 for pidx, (var, mask, val) in enumerate(self.x_vars[idx]):431 if self.solver.Value(var):432 taken.append((idx, mask))433 total_value += val434 break435 436 total_base_value = total_value437 bonus_total = 0438 for y, coeff in self.bonus_vars:439 if self.solver.Value(y):440 bonus_total += coeff441 total_value += bonus_total442 443 stats = {444 'status': status,445 'status_name': self.solver.StatusName(status),446 'objective': self.solver.ObjectiveValue(),447 'wall_time': self.solver.WallTime(),448 'base_value': total_base_value,449 'bonus_value': bonus_total,450 } 451 return total_value, taken, stats