{ "cells": [ { "cell_type": "code", "execution_count": 1, "id": "9440954a", "metadata": {}, "outputs": [], "source": [ "from random import randint\n", "\n", "capacity = 10\n", "# items are (weight, value)\n", "items = [(8,13),(3,7),(5,10),(5,10),(2,1),(2,1),(2,1)]\n", "\n", "#capacity = 20\n", "#items = [(randint(5,20),randint(5,20)) for _ in range(200)]" ] }, { "cell_type": "code", "execution_count": 6, "id": "f411bd48", "metadata": {}, "outputs": [], "source": [ "def solve(items_left, capacity_left):\n", " # return the set of items in the best solution\n", " # print(\"call with\",(items_left, capacity_left))\n", " \n", " #if not items_left:\n", " if len(items_left) == 0:\n", " return []\n", " \n", " # item = (weight, value)\n", " first_item_weight = items_left[0][0]\n", " \n", " sol_without_item = solve(items_left[1:], capacity_left)\n", " \n", " # if we have room for the first item, add it and recursively solve\n", " if first_item_weight <= capacity_left:\n", " sol_with_item = [items_left[0]] + solve(items_left[1:], capacity_left-first_item_weight)\n", " else:\n", " # if not, then only possible solution is exclusing the item\n", " return sol_without_item\n", " \n", " # compare sol_with and sol_without, and return the best\n", " score_with = sum(item[1] for item in sol_with_item)\n", " score_without = sum(item[1] for item in sol_without_item)\n", " \n", " if score_with > score_without:\n", " return sol_with_item\n", " return sol_without_item" ] }, { "cell_type": "markdown", "id": "bda8de48", "metadata": {}, "source": [ "```\n", "items = [(8,13),(3,7),(5,10)]\n", "\n", "solve([(8,13),(3,7),(5,10)], 10)\n", " --> solve([(3,7),(5,10)], 10)\n", " --> solve([(5,10)], 10)\n", " solve([(5,10)], 7)\n", " vs\n", " solve([(3,7),(5,10)], 2)\n", "```" ] }, { "cell_type": "code", "execution_count": 7, "id": "fc29be45", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(5, 10), (5, 10)]" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solve(items, capacity)" ] }, { "cell_type": "code", "execution_count": null, "id": "af21f0ba", "metadata": {}, "outputs": [], "source": [] } ], "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.10" } }, "nbformat": 4, "nbformat_minor": 5 }