{"id":468,"date":"2020-05-02T13:44:09","date_gmt":"2020-05-02T19:44:09","guid":{"rendered":"http:\/\/joshuadahl.net\/blog\/?p=468"},"modified":"2020-07-03T14:42:06","modified_gmt":"2020-07-03T20:42:06","slug":"payload","status":"publish","type":"post","link":"https:\/\/joshuadahl.net\/blog\/payload\/","title":{"rendered":"Payload"},"content":{"rendered":"<p>\t<iframe loading=\"lazy\" width=\"688\" height=\"516\" src=\"https:\/\/www.youtube.com\/embed\/fMknMZP_zX4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><br \/>\n\tMy Blue Heaven is a movie about a mobster who turns to an informant, Vinny.<br \/>\nHe ends up in witness protection and the Feds send him to a small town no one has ever heard of, in the middle of Arizona.<br \/>\nVery far away from his stomping ground of New York, and no wise guys<br \/>\nto look out for after ratting out mob bosses. Vinny notices that more and more<br \/>\nof his crew find their way to the same small town, where the naive natives<br \/>\nare not used to the slick ways of former mobsters.<\/p>\n<p>There is a scene where Vinny and his gang, tired of being goodie-two-shoes in the witness protection program, want<br \/>\nto perform a heist just like the old days. They end up ripping off a truck<br \/>\nand when they pull up the cargo doors to see what they scored, they are<br \/>\ndisappointed to find that there are no tvs, no stereos, no large cuts of meat,<br \/>\ninstead what they are left with is a full trailer of empty Culligan bottles.<\/p>\n<p>&#8220;What the hell are we supposed to do with these?&#8221; an old gangster asks<\/p>\n<p>Vinny looks at them and sees an opportunity.<\/p>\n<p>&#8220;You see the difference between you and me, I don&#8217;t see a problem here,<br \/>\nI see an opportunity.&#8221;<\/p>\n<p>If the truck hijacked were a collection of wholesale retail items headed for<br \/>\nSam&#8217;s Club one would want to load the cargo area with as many items as it could. The<br \/>\ntruck would have medium size, large size, and skinny boxes arranged in such<br \/>\na manner to delivery the maximum payload to its destination, without exceeding the weight capacity of the truck.<\/p>\n<p>However with the small weight of the empty Culligan bottle, the efficiency of the<br \/>\nload would be instead of worrying about weight, the load would have be<br \/>\narranged in such a manner to maximize number of bottles into the load<br \/>\nwithout exceeding the volume of the cargo area.<\/p>\n<p>This problem we have with our truck load can be categorized as a knapsack<br \/>\nproblem. Basically what the knapsack problem is, is pretend you are<br \/>\na burglar and you have a bag. The bag can only hold so much before it will<br \/>\ntear. Let&#8217;s say the max weight the bag can hold is W and you want<br \/>\nto maximize the score.<\/p>\n<p>Each item has a weight and a value. For instance let&#8217;s say that we<br \/>\nhave 3 items. Item A, B and C. They weigh 5lb,10lb,20lbs respectively,<br \/>\nand have a profit of $50,$60,and $140. Let&#8217;s say that our bag<br \/>\ncan only hold 30lbs obviously we can&#8217;t put them all in our bag, so what<br \/>\ndo we do? <\/p>\n<p>First define the problem so we can approach it recursively<\/p>\n<p>We have w1, w2, w3,&#8230;wn items. W as the max weight, and m[i,w] is<br \/>\nthe max value that can be added with weight less than or equal to w using<br \/>\ni items.<\/p>\n<ul>\n<li>m[0,w] = 0<\/li>\n<li>m[i,w] = m[i-1,w] if wi > w <\/li>\n<li>m[i,w] = max(m[i-1,w],m[i-1,w &#8211; wi] + vi) if wi less than or equal to w <\/li>\n<\/ul>\n<p>\nIn our simple example of three items we have W = 30 and now<br \/>\nwe have to find the entries for each row.<\/p>\n<p>For row 3 we have m[3,30], to find entries in row 2 we have <\/p>\n<p>m[3-1,30] = m[2,30] and m[3-1,30 &#8211; w3] = m[2,10]<\/p>\n<p>Now find m[2,30] similarily we have <\/p>\n<p>m[2-1,30] = m[1,30] and m[2-1,30 &#8211; w2] = m[1,20]<\/p>\n<p>Find m[2,10] we need m[2-1,10] = m[1,10] and m[2-1,10 &#8211; w2] = m[1,0]<\/p>\n<p>Fill out the table ( assuming item 1 does not exceed W )<\/p>\n<p>m[1,0] = $0<br \/>\nm[1,10] = $50<br \/>\nm[1,20] = $50<br \/>\nm[1,30] = $50<\/p>\n<p>Row two apply the formula <\/p>\n<p>m[2,10] = max(m[1,10],$60 + m[1,0] ) if w2 = 10 <= 10<br \/>\nm[1,10] if w2 = 10 > 10<br \/>\n<br \/>m[2,10] = $60<\/p>\n<p>m[2,30] = max(m[1,30], $60 + m[1,20]) if w2 = 10 <= 30<br \/>\nm[1,30] if w2 = 10 > 30 <\/p>\n<p>We get $60 + m[1,20] or $60 + $50 = $110 <\/p>\n<p>Finally row 3<\/p>\n<p>m[3,30] = max(m[2,30],$140 + m[2,10]) if w3 = 20 <= 30<br \/>\nm[2,30] if w3 = 20 > 30<\/p>\n<p>Since $140 + $60 > $110  $200 is our max profit.<\/p>\n<p>Vinny: You know, it&#8217;s dangerous for you to be here in the frozen food section.<\/p>\n<p>Shaldeen : Why is that?<\/p>\n<p>Vinny : Because you could melt all this stuff.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>My Blue Heaven is a movie about a mobster who turns to an informant, Vinny. He ends up in witness&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-468","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/joshuadahl.net\/blog\/wp-json\/wp\/v2\/posts\/468","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/joshuadahl.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/joshuadahl.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/joshuadahl.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/joshuadahl.net\/blog\/wp-json\/wp\/v2\/comments?post=468"}],"version-history":[{"count":5,"href":"https:\/\/joshuadahl.net\/blog\/wp-json\/wp\/v2\/posts\/468\/revisions"}],"predecessor-version":[{"id":481,"href":"https:\/\/joshuadahl.net\/blog\/wp-json\/wp\/v2\/posts\/468\/revisions\/481"}],"wp:attachment":[{"href":"https:\/\/joshuadahl.net\/blog\/wp-json\/wp\/v2\/media?parent=468"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/joshuadahl.net\/blog\/wp-json\/wp\/v2\/categories?post=468"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/joshuadahl.net\/blog\/wp-json\/wp\/v2\/tags?post=468"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}