{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "0a58dad2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# arguments: load capacity c, list of weights w, list of values v (and a flag for debugging output)\n",
    "#\n",
    "# precondition/contract:\n",
    "#    w and v have the same number of elements,\n",
    "#    c is a positive number,\n",
    "#    the weights w[i] are all positive numbers,\n",
    "#    and the values v[i] are all (integer or floating-point) numbers\n",
    "#\n",
    "# the function returns a list of selected items, implementing Dantzig's algorithm\n",
    "#\n",
    "def knapsack_dantzig(c, w, v, debug_output):\n",
    "    n = len(w)\n",
    "    \n",
    "    # below, we are relying on Python's built-in sorting functionality:\n",
    "    #\n",
    "    # first, a list of (v[i]/w[i], i) pairs is created;\n",
    "    # sorted() sorts that list by its first element, i.e., in ascending order of value per weight\n",
    "    # reverse() turns that list around, so that it is arranged in descending order\n",
    "    #\n",
    "    value_per_weight = sorted([(v[i]/w[i], i) for i in range(n)])\n",
    "    value_per_weight.reverse()\n",
    "    \n",
    "    selected_items = []\n",
    "    remaining_capacity = c\n",
    "    for (ratio, i) in value_per_weight:\n",
    "        if remaining_capacity >= w[i]:\n",
    "            selected_items.append(i)\n",
    "            remaining_capacity -= w[i]\n",
    "    \n",
    "    if debug_output:\n",
    "        print(\"item sorting by value-to-weight ratio, in descending order:\", value_per_weight)\n",
    "        print(\"list of selected items:\", selected_items)\n",
    "    return selected_items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "430fae53",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "capacity: 842\n",
      "weights: [178, 165, 206, 135, 97, 60, 51, 140, 3, 184, 43, 164, 91, 75, 75, 197]\n",
      "values: [78, 207, 61, 111, 68, 93, 87, 145, 224, 59, 7, 211, 167, 196, 180, 42]\n",
      "selected items:\n",
      "\t* no. 8:\tweight 3,\tvalue 224,\tvalue-to-weight ratio: 74.6667\n",
      "\t* no. 13:\tweight 75,\tvalue 196,\tvalue-to-weight ratio: 2.6133\n",
      "\t* no. 14:\tweight 75,\tvalue 180,\tvalue-to-weight ratio: 2.4\n",
      "\t* no. 12:\tweight 91,\tvalue 167,\tvalue-to-weight ratio: 1.8352\n",
      "\t* no. 6:\tweight 51,\tvalue 87,\tvalue-to-weight ratio: 1.7059\n",
      "\t* no. 5:\tweight 60,\tvalue 93,\tvalue-to-weight ratio: 1.55\n",
      "\t* no. 11:\tweight 164,\tvalue 211,\tvalue-to-weight ratio: 1.2866\n",
      "\t* no. 1:\tweight 165,\tvalue 207,\tvalue-to-weight ratio: 1.2545\n",
      "\t* no. 7:\tweight 140,\tvalue 145,\tvalue-to-weight ratio: 1.0357\n",
      "total weight: 824\n",
      "total value: 1510\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "capacity = random.randrange(1024)\n",
    "weights = [random.randrange(1, 256) for i in range(16)]\n",
    "values = [random.randrange(1, 256) for i in range(16)]\n",
    "\n",
    "print(\"capacity:\", capacity)\n",
    "print(\"weights:\", weights)\n",
    "print(\"values:\", values)\n",
    "\n",
    "selected = knapsack_dantzig(capacity, weights, values, False)\n",
    "print(\"selected items:\")\n",
    "total_weight = 0\n",
    "total_value = 0\n",
    "for i in selected:\n",
    "    total_weight += weights[i]\n",
    "    total_value += values[i]\n",
    "    print(\"\\t* no. \", i, \":\\tweight \", weights[i],\\\n",
    "          \",\\tvalue \", values[i], \",\\tvalue-to-weight ratio: \",\\\n",
    "          round(values[i]/weights[i], 4), sep=\"\")\n",
    "print(\"total weight:\", total_weight)\n",
    "print(\"total value:\", total_value)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}