Standard problem of trying to maximize the values of item with a constraint.\u00a0 How many items can you put in a knapsack given the value and the weight of the items.<\/p>\n
Uses python3
\ngoal: maximize the value of items selected from the get_optimal_value
\nwhile the items selected combined weight is less than the inputted capacity<\/p>\n
<\/p>\n
import sys\r\nfrom array import array\r\n\r\ndef getIndex(item):\r\n return item[0]\r\n\r\ndef getKey(item):\r\n return item[1]\r\n\r\ndef get_optimal_value(capacity, weights, values):\r\n total_value = 0.\r\n values_per_unit = list()\r\n # write your code here\r\n for counter in range(0, len(weights)):\r\n #print(counter, values[counter], weights[counter], values[counter]\/weights[counter])\r\n values_per_unit.insert(counter,[counter,values[counter] \/ weights[counter]])\r\n\r\n values_per_unit.sort(key=getKey ,reverse = True)\r\n # print(values_per_unit)\r\n\r\n # grab max of each item until hit capacity\r\n for counter in range(0, len(weights)):\r\n capacity_to_add = min(capacity, weights[getIndex(values_per_unit[counter])])\r\n #print(capacity, capacity_to_add, values_per_unit[counter])\r\n\r\n value_to_add = getKey(values_per_unit[counter]) * capacity_to_add\r\n #print(\"total value: \", total_value, \"value to add: \", value_to_add)\r\n total_value = total_value + getKey(values_per_unit[counter]) * capacity_to_add\r\n capacity = capacity - capacity_to_add\r\n\r\n if capacity <= 0:\r\n return total_value\r\n return total_value\r\n\r\n# user_input_items_n: number of items to choose from\r\n# user_input_capacity: total max value of items choosen\r\n# item_values: vector, value of item\r\n# item_weights: vector, weight of item\r\ndef user_input():\r\n # get the values from the user\r\n data = list(map(int, sys.stdin.read().split()))\r\n # split the number of items and weight value\r\n user_input_items_n, user_input_capacity = data[0:2]\r\n item_values = data[2:(2 * user_input_items_n + 2):2]\r\n item_weights = data[3:(2 * user_input_items_n + 2):2]\r\n opt_value = get_optimal_value(user_input_capacity, item_weights, item_values)\r\n \r\n # output the value formatted with 4 decimal points\r\n print(\"{:.4f}\".format(opt_value))\r\n\r\n# run main program\r\nif __name__ == \"__main__\":\r\n user_input()<\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
Standard problem of trying to maximize the values of item with a constraint.\u00a0 How many items can you put in a knapsack given the value and the weight of the items. Uses python3 goal: maximize the value of items selected from the get_optimal_value while the items selected combined weight is less than the inputted capacity<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_crdt_document":"","footnotes":""},"categories":[3,4],"tags":[28,30,32],"series":[],"class_list":["post-136","post","type-post","status-publish","format-standard","hentry","category-python","category-code","tag-python","tag-code","tag-fractional-knapsack"],"_links":{"self":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/136","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/comments?post=136"}],"version-history":[{"count":3,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/136\/revisions"}],"predecessor-version":[{"id":139,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/136\/revisions\/139"}],"wp:attachment":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/media?parent=136"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/categories?post=136"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/tags?post=136"},{"taxonomy":"series","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/series?post=136"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}