coding-hometask-1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# Задание по курсу «Дискретная оптимизация», МФТИ, весна 2017"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Задача 1-1\n",
    "## Учимся переводить между decision/evaluation/search на примере Bin Packing\n",
    "\n",
    "**Даны:** \n",
    "* $[w_1, \\dots , w_k], w_i \\in [0, 1]$ — веса грузов  \n",
    "* $n_{\\text{bins}}$ — количество корзин грузоподъемностью 1.\n",
    "\n",
    "Предполагается, что функция `solve_bp_decision(weights, n_bins)` решает «распознавательный» (decision) вариант задачи bin packing. На вход ей подаётся список весов и число корзин. Функция возвращает булевский ответ на вопрос «можно ли заданные веса раскидать по не более чем `n_bins` контейнерам? \n",
    "\n",
    "Напишите содержимое функции `solve_bp_evaluation`, которая возвращает оптимальное число корзин (решает evaluation variant задачи bin packing). \n",
    "\n",
    "Затем напишите содержимое функции `solve_bp_search`, которая возвращает список номеров корзин, которые при каком-нибудь оптимальном распределении присваиваются весам из списка `weights` (корзины нумеруются с единицы). \n",
    "\n",
    "Каждая из следующих функций должна вызывать предыдущую не более чем полиномиальное число раз."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def solve_bp_decision(weights: list, n_bins: int) -> bool:\n",
    "    def able_to_pack(weights: list, bin_capacities) -> bool:\n",
    "        return weights == [] or any( \n",
    "            able_to_pack( weights[:-1], bin_capacities[:i] + [capacity - weights[-1]] + bin_capacities[(i + 1):] ) \n",
    "            for i, capacity in enumerate(bin_capacities) if capacity >= weights[-1] \n",
    "        )\n",
    "\n",
    "    return able_to_pack( sorted(weights), [1.0] * n_bins )\n",
    "\n",
    "# To test this, run:\n",
    "# solve_bp_decision([0.8, 0.09, 0.4, 0.7], 2)\n",
    "# solve_bp_decision([0.8, 0.09, 0.4, 0.7], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def solve_bp_evaluation(weights: list) -> int:\n",
    "    # Вырожденный случай.\n",
    "    if len(weights) == 0:\n",
    "        return 0\n",
    "    \n",
    "    left = 0\n",
    "    # Нам точно хватит столько же корзин, сколько весов --\n",
    "    # просто положим каждый элемент в отдельную корзину.\n",
    "    right = len(weights)\n",
    "    # В бинпоиске по допустимому числу корзин сохраняется инвариант:\n",
    "    # solve_bp_decision(weights, left) = False,\n",
    "    # solve_bp_decision(weights, right) = True.\n",
    "    # Число вызовов solve_bp_decision -- O(log(len(weights))).\n",
    "    while left < right - 1:\n",
    "        median = (left + right) // 2\n",
    "        if solve_bp_decision(weights, median):\n",
    "            right = median\n",
    "        else:\n",
    "            left = median\n",
    "    min_n_bins = right\n",
    "    return min_n_bins"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def solve_bp_search(weights: list):\n",
    "    weights_mutable = weights\n",
    "    n_weights = len(weights)\n",
    "    n_bins_optimal = solve_bp_evaluation(weights)\n",
    "    \n",
    "    solution = [0] * n_weights\n",
    "    # Для всех весов до обладающего данным номером уже определены корзины.\n",
    "    not_solved = 0\n",
    "    # Первая корзина, которую заполнили не полностью.\n",
    "    not_full = 1\n",
    "    \n",
    "    # На каждом нетривиальном шаге цикла мы заполняем корзину:\n",
    "    # вес, который еще не был куда-то положен, кладется в эту корзину\n",
    "    # (должен же он где-то лежать), после чего мы смотрим, можем ли мы\n",
    "    # добавить еще один вес с неопределенной корзиной к нему,\n",
    "    # не нарушая оптимальности. Если да, то мы можем считать,\n",
    "    # что объединение весов является одним весом;\n",
    "    # в weights_mutable пара элементов заменяется одним,\n",
    "    # а на место второго элемента ставится 0, который\n",
    "    # не влияет на решение.\n",
    "    # Число вызовов solve_bp_evaluation не превышает n * (n - 1) / 2.\n",
    "    for not_solved in range(n_weights):\n",
    "        # Случай, когда для веса была уже определена корзина.\n",
    "        if solution[not_solved] != 0:\n",
    "            continue\n",
    "        \n",
    "        solution[not_solved] = not_full\n",
    "        for i in range(not_solved + 1, n_weights):\n",
    "            if solution[i] != 0:\n",
    "                continue\n",
    "            \n",
    "            # Вес, который мы добавим в корзину к изучаемому.\n",
    "            add_weight = weights_mutable[i]\n",
    "            if add_weight + weights_mutable[not_solved] > 1:\n",
    "                continue\n",
    "            \n",
    "            weights_mutable[not_solved] += add_weight\n",
    "            weights_mutable[i] = 0\n",
    "            \n",
    "            if solve_bp_evaluation(weights_mutable) == n_bins_optimal:\n",
    "                solution[i] = not_full\n",
    "            else:\n",
    "                weights_mutable[not_solved] -= add_weight\n",
    "                weights_mutable[i] = add_weight\n",
    "        \n",
    "        not_full += 1\n",
    "    \n",
    "        \n",
    "    return solution # list"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}