{"id":635,"date":"2013-07-31T08:32:12","date_gmt":"2013-07-31T07:32:12","guid":{"rendered":"http:\/\/oprsteny.cz\/?p=635"},"modified":"2014-03-04T20:38:22","modified_gmt":"2014-03-04T19:38:22","slug":"algorithms-puzzle-called-knapsack","status":"publish","type":"post","link":"https:\/\/oprsteny.cz\/?p=635","title":{"rendered":"Algorithms &#8211; puzzle called Knapsack"},"content":{"rendered":"<p><img loading=\"lazy\" decoding=\"async\" data-attachment-id=\"640\" data-permalink=\"https:\/\/oprsteny.cz\/?attachment_id=640\" data-orig-file=\"https:\/\/oprsteny.cz\/wp-content\/uploads\/knapsack.jpg\" data-orig-size=\"186,271\" data-comments-opened=\"1\" data-image-meta=\"{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;}\" data-image-title=\"Knapsack Puzzle\" data-image-description=\"\" data-image-caption=\"\" data-large-file=\"https:\/\/oprsteny.cz\/wp-content\/uploads\/knapsack.jpg\" class=\"alignleft  wp-image-640\" alt=\"Knapsack Puzzle\" src=\"http:\/\/oprsteny.cz\/wp-content\/uploads\/knapsack-150x150.jpg\" width=\"90\" height=\"90\" \/>Today I&#8217;d like to share with you a puzzle I managed to solve in past few weeks using a technique called branch&amp;bound &#8211; Knapsack.<\/p>\n<p>Interested what is 0-1 Knapsack puzzle about?\u00a0<!--more--><\/p>\n<p>The\u00a0<b>knapsack problem<\/b>\u00a0(or\u00a0<b>rucksack problem)<\/b>\u00a0is a problem in\u00a0combinatorial optimization: Given a set of items, each with a mass and a value, determine for each item if it can be included in a collection so that the total weight is less than or equal to a given limit (capacity of rucksack) and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size\u00a0knapsack\u00a0and must fill it with the most valuable items &#8211; i.e. Indiana Jones \ud83d\ude42<\/p>\n<p>The problem often arises in\u00a0resource allocation\u00a0where there are financial constraints and is studied in fields such as\u00a0combinatorics,\u00a0computer science,\u00a0complexity theory,\u00a0cryptography\u00a0and\u00a0applied mathematics.<\/p>\n<p>The most common problem being solved is the\u00a0<strong>0-1 knapsack problem<\/strong>, which restricts the number\u00a0<i>x<sub>i<\/sub><\/i>\u00a0of copies of each kind of item to zero or one.<\/p>\n<p>Mathematically the 0-1-knapsack problem can be formulated as:<\/p>\n<ul>\n<li>Let there be <em>n<\/em>\u00a0items, <i>x<sub>1<\/sub><\/i> to\u00a0<i>x<sub>n<\/sub><\/i>\u00a0where\u00a0<i>x<sub>i<\/sub><\/i>\u00a0has a value\u00a0<i>v<sub>i<\/sub><\/i>\u00a0and weight\u00a0<i>w<sub>i<\/sub><\/i><\/li>\n<li>The maximum weight that we can carry in the bag is\u00a0<i>W<\/i><\/li>\n<li>It is common to assume that all values and weights are non negative<\/li>\n<li>To simplify the representation, we also assume that the items are listed in increasing order of weight.<\/li>\n<\/ul>\n<ul>\n<li>Solution is to maximize\u00a0<img decoding=\"async\" alt=\"Knapsack target\" src=\"http:\/\/oprsteny.cz\/wp-content\/uploads\/knapsack_target.png\" height=\"30\" \/>\u00a0subject to <img decoding=\"async\" alt=\"Knapsack condition\" src=\"http:\/\/oprsteny.cz\/wp-content\/uploads\/knapsack_condition.png\" height=\"30\" \/><\/li>\n<li>Said by human language: Maximize the sum of the values of the items in the knapsack so that the sum of the weights must be less than the knapsack&#8217;s capacity.<\/li>\n<\/ul>\n<h2>Solution spoiler in Python<\/h2>\n<p>Simple knapsack solution:<\/p>\n<p><a href=\"http:\/\/oprsteny.cz\/wp-content\/uploads\/knapsack_solution1.png\"><img loading=\"lazy\" decoding=\"async\" data-attachment-id=\"639\" data-permalink=\"https:\/\/oprsteny.cz\/?attachment_id=639\" data-orig-file=\"https:\/\/oprsteny.cz\/wp-content\/uploads\/knapsack_solution1.png\" data-orig-size=\"458,352\" data-comments-opened=\"1\" data-image-meta=\"{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;}\" data-image-title=\"Knapsack solution\" data-image-description=\"\" data-image-caption=\"\" data-large-file=\"https:\/\/oprsteny.cz\/wp-content\/uploads\/knapsack_solution1.png\" class=\"size-thumbnail wp-image-639 alignnone\" alt=\"Knapsack solution\" src=\"http:\/\/oprsteny.cz\/wp-content\/uploads\/knapsack_solution1-150x150.png\" width=\"150\" height=\"150\" \/><\/a><\/p>\n<p>Input data to function <em>solveKnapsack<\/em> are in format<br \/>\nN W<br \/>\nv<sub>1<\/sub> w<sub>1<\/sub><br \/>\nv<sub>2<\/sub> w<sub>2<\/sub><br \/>\n&#8230;.<br \/>\nv<sub>n-1<\/sub> w<sub>n-1<\/sub><br \/>\nWhere <em>N<\/em> is number of items, <em>W<\/em> is capacity of knapsack.<br \/>\nEach of the following lines contains value <em>v<\/em> and weight <em>w<\/em> of an item.<\/p>\n<pre lang=\"python\">class Item:\r\n    def __init__(self, v=0, w=0, w_v=0, idx=0):\r\n        self.value = v\r\n        self.weight = w\r\n        self.importance = w_v\r\n        self.original_order = idx\r\n\r\nclass State:\r\n    def __init__(self, item_index = 0, current_value=0, remaining_capacity =0, max_possible_value = 0, path = \"\"):\r\n        self.item_index = item_index\r\n        self.current_value = current_value\r\n        self.remaining_capacity = remaining_capacity\r\n        self.max_possible_value = max_possible_value\r\n        self.path = path\r\n# Function that returns maximal possible gain for items\r\n# that are still not processed and for given capacity\r\ndef getMaxPossible(items, item_index, current_value, capacity):\r\n    max_possible = 0\r\n    for i in range(item_index, len(items)):\r\n# If the capacity is less than weight of the item,\r\n# we add \"part\" of the value equal to \"part\" of the weight of the item\r\n        if items[i].weight &gt; capacity:\r\n            max_possible += float(items[i].importnace) * capacity\r\n            break\r\n        else:\r\n            max_possible += items[i].value\r\n            capacity -= items[i].weight\r\n\r\n    return int(max_possible+0.5)+current_value\r\n\r\n# Iterative Knapsack solution\r\n# using Depth First Branch&amp;Bound\r\ndef knapsack_DFS(items, max_capacity):\r\n    optimal_value = 0\r\n    target = 0\r\n    optimal_path = \"\"\r\n    num_items = len(items)\r\n\r\n# Sort all items by their importance\r\n    items.sort(key=lambda x: x.importance, reverse=True)\r\n\r\n# Initial status of the knapsack\r\n    states = [State(0,0,max_capacity,getMaxPossible(items,0,0,max_capacity), \"\")]\r\n\r\n# Compute while there's any unprocessed status\r\n    while(len(states)!=0):\r\n# Get the last inserted status\r\n        best = states.pop()\r\n\r\n# We're processing the last item\r\n        if best.item_index == num_items-1:\r\n\r\n# We can add the item in the bag\r\n            if best.remaining_capacity &gt;= items[best.item_index].weight:\r\n\r\n# Item added to the bag gives us the best solution found so far\r\n                if best.max_possible_value &gt;= target:\r\n                    optimal_value = best.max_possible_value\r\n                    target = optimal_value + 1\r\n                    optimal_path = ','.join(filter(None, [best.path, str(items[best.item_index].original_order)]))\r\n\r\n# We can't add the item into the bag\r\n            else:\r\n\r\n# Is the solution we found better than the one we've found so far?\r\n                if best.current_value &gt;= target:\r\n                    optimal_value = best.current_value\r\n                    target = optimal_value + 1\r\n                    optimal_path = best.path\r\n\r\n# Delete all states from queue where the max possible gain is less than gain we reached in the current processing\r\n            states = [s for s in states if s.max_possible_value &gt;= target]\r\n\r\n# We're not processing the last item\r\n        else:\r\n# A) We don't add item in the bag\r\n# Recalculate new maximal possible gain\r\n            new_max_possible = getMaxPossible(items, best.item_index+1, best.current_value, best.remaining_capacity)\r\n# Can we do better ?\r\n            if new_max_possible &gt;= target:\r\n                states.append(State(\r\n                    best.item_index+1,\r\n                    best.current_value,\r\n                    best.remaining_capacity,\r\n                    new_max_possible,\r\n                    best.path\r\n                    )\r\n                )\r\n\r\n# B) We add item in the bag\r\n            if best.remaining_capacity &gt;= items[best.item_index].weight and best.max_possible_value &gt;= target:\r\n                states.append(State(\r\n                    best.item_index+1,\r\n                    best.current_value+items[best.item_index].value,\r\n                    best.remaining_capacity - items[best.item_index].weight,\r\n                    best.max_possible_value,\r\n                    ','.join(filter(None, [best.path, str(items[best.item_index].original_order)]))\r\n                    )\r\n                )\r\n\r\n# Format output data\r\n# 1. Optimal value of items added into knapsack\r\n    outputData = str(optimal_value) + '\\n'\r\n    if optimal_path == \"\":\r\n        optimal_path = \"0\"\r\n# For each item print 1\/0 = added\/not added into knapsack\r\n    picked_list = [x for x in map(int, optimal_path.split(','))]\r\n    picked = \"\"\r\n    for x in range(num_items):\r\n        if x in picked_list:\r\n            picked += \"1\"\r\n        else:\r\n            picked += \"0\"\r\n    outputData += \" \".join(picked)\r\n    return outputData\r\n\r\ndef solveKnapsack(inputData):\r\n    lines = inputData.split('\\n')\r\n\r\n    firstLine = lines[0].split()\r\n    num_items = int(firstLine[0])\r\n    max_capacity = int(firstLine[1])\r\n    items = list()\r\n    for i in range(1, num_items+1):\r\n        line = lines[i]\r\n        parts = line.split()\r\n\r\n# Compute item importance (value\/weight)\r\n        w_v = 0\r\n        if int(parts[1]) != 0:\r\n            w_v = float(parts[0])\/float(parts[1])\r\n        items.append(knapsack.Item(int(parts[0]), int(parts[1]), w_v, i-1))\r\n\r\n    del inputData\r\n    del lines\r\n    return knapsack_DFS(items, max_capacity)<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Today I&#8217;d like to share with you a puzzle I managed to solve in past few weeks using a technique called branch&amp;bound &#8211; Knapsack. Interested what is 0-1 Knapsack puzzle about?\u00a0<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"Algorithms - puzzle called Knapsack","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[15,9,172],"tags":[178,176,175,180,179,173,174,158,177],"class_list":["post-635","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-development","category-python","tag-algorithm","tag-best-first-search","tag-bfs","tag-branch-and-bound","tag-dynamic-programming","tag-knapsack","tag-optimization","tag-puzzle","tag-rucksack"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p3nYbe-af","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/oprsteny.cz\/index.php?rest_route=\/wp\/v2\/posts\/635","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oprsteny.cz\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/oprsteny.cz\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/oprsteny.cz\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/oprsteny.cz\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=635"}],"version-history":[{"count":3,"href":"https:\/\/oprsteny.cz\/index.php?rest_route=\/wp\/v2\/posts\/635\/revisions"}],"predecessor-version":[{"id":941,"href":"https:\/\/oprsteny.cz\/index.php?rest_route=\/wp\/v2\/posts\/635\/revisions\/941"}],"wp:attachment":[{"href":"https:\/\/oprsteny.cz\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=635"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oprsteny.cz\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=635"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oprsteny.cz\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=635"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}