{"id":3171,"date":"2025-06-07T10:39:12","date_gmt":"2025-06-07T10:39:12","guid":{"rendered":"https:\/\/diznr.com\/?p=3171"},"modified":"2025-06-07T10:39:12","modified_gmt":"2025-06-07T10:39:12","slug":"knapsack-problem-of-greedy-method-understand-with-real-example-life","status":"publish","type":"post","link":"https:\/\/www.reilsolar.com\/pdf\/knapsack-problem-of-greedy-method-understand-with-real-example-life\/","title":{"rendered":"Knapsack problem of Greedy method [ understand with real life example]."},"content":{"rendered":"<p>Knapsack problem of Greedy method [ understand with real life example].<\/p>\n<p>[fvplayer id=&#8221;284&#8243;]<\/p>\n<h3 class=\"\" data-start=\"0\" data-end=\"72\">\ud83c\udf92 <strong data-start=\"7\" data-end=\"72\">Knapsack Problem using Greedy Method \u2014 with Real-Life Example<\/strong><\/h3>\n<hr class=\"\" data-start=\"74\" data-end=\"77\" \/>\n<h3 class=\"\" data-start=\"79\" data-end=\"118\">\u2705 <strong data-start=\"85\" data-end=\"118\">What is the Knapsack Problem?<\/strong><\/h3>\n<p class=\"\" data-start=\"120\" data-end=\"162\">It\u2019s a classic optimization problem where:<\/p>\n<ul data-start=\"163\" data-end=\"386\">\n<li class=\"\" data-start=\"163\" data-end=\"246\">\n<p class=\"\" data-start=\"165\" data-end=\"246\">You have a <strong data-start=\"176\" data-end=\"194\">bag (knapsack)<\/strong> that can carry up to a certain <strong data-start=\"226\" data-end=\"245\">weight\/capacity<\/strong>.<\/p>\n<\/li>\n<li class=\"\" data-start=\"247\" data-end=\"308\">\n<p class=\"\" data-start=\"249\" data-end=\"308\">You have <strong data-start=\"258\" data-end=\"267\">items<\/strong>, each with a <strong data-start=\"281\" data-end=\"291\">weight<\/strong> and a <strong data-start=\"298\" data-end=\"307\">value<\/strong>.<\/p>\n<\/li>\n<li class=\"\" data-start=\"309\" data-end=\"386\">\n<p class=\"\" data-start=\"311\" data-end=\"386\">The goal is to <strong data-start=\"326\" data-end=\"350\">maximize total value<\/strong> <strong data-start=\"351\" data-end=\"385\">without exceeding the capacity<\/strong>.<\/p>\n<\/li>\n<\/ul>\n<hr class=\"\" data-start=\"388\" data-end=\"391\" \/>\n<h3 class=\"\" data-start=\"393\" data-end=\"439\">\u2699\ufe0f <strong data-start=\"400\" data-end=\"439\">Greedy Method (Fractional Knapsack)<\/strong><\/h3>\n<p class=\"\" data-start=\"441\" data-end=\"473\">In the <strong data-start=\"448\" data-end=\"467\">Greedy approach<\/strong>, you:<\/p>\n<ul data-start=\"474\" data-end=\"680\">\n<li class=\"\" data-start=\"474\" data-end=\"559\">\n<p class=\"\" data-start=\"476\" data-end=\"559\">Choose items with the <strong data-start=\"498\" data-end=\"531\">highest value per unit weight<\/strong> (value\/weight ratio) first.<\/p>\n<\/li>\n<li class=\"\" data-start=\"560\" data-end=\"615\">\n<p class=\"\" data-start=\"562\" data-end=\"615\">You can <strong data-start=\"570\" data-end=\"588\">take fractions<\/strong> of items (not whole only).<\/p>\n<\/li>\n<li class=\"\" data-start=\"616\" data-end=\"680\">\n<p class=\"\" data-start=\"618\" data-end=\"680\">It&#8217;s optimal for <strong data-start=\"635\" data-end=\"658\">fractional knapsack<\/strong>, not for 0\/1 version.<\/p>\n<\/li>\n<\/ul>\n<hr class=\"\" data-start=\"682\" data-end=\"685\" \/>\n<h3 class=\"\" data-start=\"687\" data-end=\"742\">\ud83d\udccc <strong data-start=\"694\" data-end=\"742\">Real-Life Example: Emergency Relief Backpack<\/strong><\/h3>\n<p class=\"\" data-start=\"744\" data-end=\"869\">Imagine you&#8217;re packing an <strong data-start=\"770\" data-end=\"794\">emergency relief bag<\/strong> during a disaster. The bag can hold up to <strong data-start=\"837\" data-end=\"846\">15 kg<\/strong>. You have these items:<\/p>\n<div class=\"_tableContainer_16hzy_1\">\n<div class=\"_tableWrapper_16hzy_14 group flex w-fit flex-col-reverse\">\n<table class=\"w-fit min-w-(--thread-content-width)\" data-start=\"871\" data-end=\"1288\">\n<thead data-start=\"871\" data-end=\"937\">\n<tr data-start=\"871\" data-end=\"937\">\n<th data-start=\"871\" data-end=\"886\" data-col-size=\"sm\">Item<\/th>\n<th data-start=\"886\" data-end=\"900\" data-col-size=\"sm\">Weight (kg)<\/th>\n<th data-start=\"900\" data-end=\"921\" data-col-size=\"sm\">Value (Importance)<\/th>\n<th data-start=\"921\" data-end=\"937\" data-col-size=\"sm\">Value\/Weight<\/th>\n<\/tr>\n<\/thead>\n<tbody data-start=\"1009\" data-end=\"1288\">\n<tr data-start=\"1009\" data-end=\"1078\">\n<td data-start=\"1009\" data-end=\"1025\" data-col-size=\"sm\">First Aid Kit<\/td>\n<td data-col-size=\"sm\" data-start=\"1025\" data-end=\"1039\">3<\/td>\n<td data-col-size=\"sm\" data-start=\"1039\" data-end=\"1061\">60<\/td>\n<td data-col-size=\"sm\" data-start=\"1061\" data-end=\"1078\">20.0<\/td>\n<\/tr>\n<tr data-start=\"1079\" data-end=\"1148\">\n<td data-start=\"1079\" data-end=\"1095\" data-col-size=\"sm\">Bottled Water<\/td>\n<td data-start=\"1095\" data-end=\"1109\" data-col-size=\"sm\">5<\/td>\n<td data-col-size=\"sm\" data-start=\"1109\" data-end=\"1131\">100<\/td>\n<td data-col-size=\"sm\" data-start=\"1131\" data-end=\"1148\">20.0<\/td>\n<\/tr>\n<tr data-start=\"1149\" data-end=\"1218\">\n<td data-start=\"1149\" data-end=\"1165\" data-col-size=\"sm\">Food Pack<\/td>\n<td data-col-size=\"sm\" data-start=\"1165\" data-end=\"1179\">7<\/td>\n<td data-col-size=\"sm\" data-start=\"1179\" data-end=\"1201\">140<\/td>\n<td data-col-size=\"sm\" data-start=\"1201\" data-end=\"1218\">20.0<\/td>\n<\/tr>\n<tr data-start=\"1219\" data-end=\"1288\">\n<td data-start=\"1219\" data-end=\"1235\" data-col-size=\"sm\">Flashlight<\/td>\n<td data-start=\"1235\" data-end=\"1249\" data-col-size=\"sm\">2<\/td>\n<td data-col-size=\"sm\" data-start=\"1249\" data-end=\"1271\">30<\/td>\n<td data-col-size=\"sm\" data-start=\"1271\" data-end=\"1288\">15.0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div class=\"sticky end-(--thread-content-margin) h-0 self-end select-none\">\n<div class=\"absolute end-0 flex items-end\"><\/div>\n<\/div>\n<\/div>\n<\/div>\n<hr class=\"\" data-start=\"1290\" data-end=\"1293\" \/>\n<h3 class=\"\" data-start=\"1295\" data-end=\"1333\">\ud83e\udde0 <strong data-start=\"1302\" data-end=\"1333\">Step-by-step Greedy Method:<\/strong><\/h3>\n<ol data-start=\"1335\" data-end=\"1478\">\n<li class=\"\" data-start=\"1335\" data-end=\"1420\">\n<p class=\"\" data-start=\"1338\" data-end=\"1375\"><strong data-start=\"1338\" data-end=\"1375\">Sort items by value\/weight ratio:<\/strong><\/p>\n<ul data-start=\"1379\" data-end=\"1420\">\n<li class=\"\" data-start=\"1379\" data-end=\"1420\">\n<p class=\"\" data-start=\"1381\" data-end=\"1420\">All have 20.0, except flashlight (15.0)<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<li class=\"\" data-start=\"1421\" data-end=\"1478\">\n<p class=\"\" data-start=\"1424\" data-end=\"1478\"><strong data-start=\"1424\" data-end=\"1478\">Start filling the bag with items of highest ratio:<\/strong><\/p>\n<\/li>\n<\/ol>\n<ul data-start=\"1480\" data-end=\"1686\">\n<li class=\"\" data-start=\"1480\" data-end=\"1547\">\n<p class=\"\" data-start=\"1482\" data-end=\"1547\">Take <strong data-start=\"1487\" data-end=\"1511\">First Aid Kit (3 kg)<\/strong> \u2192 total weight = 3 kg, value = 60<\/p>\n<\/li>\n<li class=\"\" data-start=\"1548\" data-end=\"1616\">\n<p class=\"\" data-start=\"1550\" data-end=\"1616\">Take <strong data-start=\"1555\" data-end=\"1579\">Bottled Water (5 kg)<\/strong> \u2192 total weight = 8 kg, value = 160<\/p>\n<\/li>\n<li class=\"\" data-start=\"1617\" data-end=\"1686\">\n<p class=\"\" data-start=\"1619\" data-end=\"1686\">Take <strong data-start=\"1624\" data-end=\"1644\">Food Pack (7 kg)<\/strong> \u2192 total weight = 15 kg (max), value = 300<\/p>\n<\/li>\n<\/ul>\n<p class=\"\" data-start=\"1688\" data-end=\"1775\">\u2705 Total weight used = 15 kg<br data-start=\"1715\" data-end=\"1718\" \/>\u2705 Total value gained = <strong data-start=\"1741\" data-end=\"1748\">300<\/strong><br data-start=\"1748\" data-end=\"1751\" \/>(No room for Flashlight)<\/p>\n<hr class=\"\" data-start=\"1777\" data-end=\"1780\" \/>\n<h3 class=\"\" data-start=\"1782\" data-end=\"1833\">\ud83d\udd04 <strong data-start=\"1789\" data-end=\"1831\">If only 2 kg space left for Food Pack?<\/strong><\/h3>\n<p class=\"\" data-start=\"1834\" data-end=\"1882\">Take 2\/7 of it:<br data-start=\"1849\" data-end=\"1852\" \/>\u2192 Value = (2\/7) \u00d7 140 = <strong data-start=\"1876\" data-end=\"1882\">40<\/strong><\/p>\n<hr class=\"\" data-start=\"1884\" data-end=\"1887\" \/>\n<h3 class=\"\" data-start=\"1889\" data-end=\"1922\">\ud83e\uddfe <strong data-start=\"1896\" data-end=\"1922\">Why Greedy Works Here?<\/strong><\/h3>\n<ul data-start=\"1923\" data-end=\"2019\">\n<li class=\"\" data-start=\"1923\" data-end=\"1956\">\n<p class=\"\" data-start=\"1925\" data-end=\"1956\">Fractional choices are allowed.<\/p>\n<\/li>\n<li class=\"\" data-start=\"1957\" data-end=\"2019\">\n<p class=\"\" data-start=\"1959\" data-end=\"2019\">Maximizing value per kg works best when dividing is allowed.<\/p>\n<\/li>\n<\/ul>\n<hr class=\"\" data-start=\"2021\" data-end=\"2024\" \/>\n<h3 class=\"\" data-start=\"2026\" data-end=\"2055\">\u274c <strong data-start=\"2032\" data-end=\"2055\">Where Greedy Fails?<\/strong><\/h3>\n<p class=\"\" data-start=\"2056\" data-end=\"2180\">In <strong data-start=\"2059\" data-end=\"2075\">0\/1 Knapsack<\/strong> (items can&#8217;t be split), greedy may not give the best solution. There, <strong data-start=\"2146\" data-end=\"2169\">Dynamic Programming<\/strong> is better.<\/p>\n<hr class=\"\" data-start=\"2182\" data-end=\"2185\" \/>\n<h3 class=\"\" data-start=\"2187\" data-end=\"2202\">\ud83d\udca1 Summary:<\/h3>\n<div class=\"_tableContainer_16hzy_1\">\n<div class=\"_tableWrapper_16hzy_14 group flex w-fit flex-col-reverse\">\n<table class=\"w-fit min-w-(--thread-content-width)\" data-start=\"2204\" data-end=\"2439\">\n<thead data-start=\"2204\" data-end=\"2249\">\n<tr data-start=\"2204\" data-end=\"2249\">\n<th data-start=\"2204\" data-end=\"2222\" data-col-size=\"sm\">\ud83d\udccc Concept<\/th>\n<th data-start=\"2222\" data-end=\"2249\" data-col-size=\"sm\">\u2705 Greedy Approach Works<\/th>\n<\/tr>\n<\/thead>\n<tbody data-start=\"2296\" data-end=\"2439\">\n<tr data-start=\"2296\" data-end=\"2341\">\n<td data-start=\"2296\" data-end=\"2315\" data-col-size=\"sm\">Fractional items<\/td>\n<td data-col-size=\"sm\" data-start=\"2315\" data-end=\"2341\">\u2705 Yes<\/td>\n<\/tr>\n<tr data-start=\"2342\" data-end=\"2388\">\n<td data-start=\"2342\" data-end=\"2361\" data-col-size=\"sm\">0\/1 items<\/td>\n<td data-col-size=\"sm\" data-start=\"2361\" data-end=\"2388\">\u274c Not always optimal<\/td>\n<\/tr>\n<tr data-start=\"2389\" data-end=\"2439\">\n<td data-start=\"2389\" data-end=\"2408\" data-col-size=\"sm\">Real-life fit<\/td>\n<td data-col-size=\"sm\" data-start=\"2408\" data-end=\"2439\">\u2705 Packing, resource loading<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div class=\"sticky end-(--thread-content-margin) h-0 self-end select-none\">\n<div class=\"absolute end-0 flex items-end\"><\/div>\n<\/div>\n<\/div>\n<\/div>\n<hr class=\"\" data-start=\"2441\" data-end=\"2444\" \/>\n<p class=\"\" data-start=\"2446\" data-end=\"2461\">Would you like:<\/p>\n<ul data-start=\"2462\" data-end=\"2565\" data-is-last-node=\"\" data-is-only-node=\"\">\n<li class=\"\" data-start=\"2462\" data-end=\"2495\">\n<p class=\"\" data-start=\"2464\" data-end=\"2495\">A visual chart of this example?<\/p>\n<\/li>\n<li class=\"\" data-start=\"2496\" data-end=\"2531\">\n<p class=\"\" data-start=\"2498\" data-end=\"2531\">Practice problems with solutions?<\/p>\n<\/li>\n<li class=\"\" data-start=\"2532\" data-end=\"2565\">\n<p class=\"\" data-start=\"2534\" data-end=\"2565\">A version for <strong data-start=\"2548\" data-end=\"2564\">0\/1 knapsack<\/strong>?<\/p>\n<\/li>\n<\/ul>\n<h3><a href=\"https:\/\/www.acsce.edu.in\/acsce\/wp-content\/uploads\/2020\/03\/Module3_DAA.pdf\" target=\"_blank\" rel=\"noopener\">Knapsack problem of Greedy method [ understand with real life example].<\/a><\/h3>\n<h3 class=\"LC20lb MBeuO DKV0Md\"><a href=\"https:\/\/www.mathsjournal.com\/pdf\/2019\/vol4issue3\/PartA\/4-3-6-282.pdf\" target=\"_blank\" rel=\"noopener\">Greedy solution method for knapsack problems with R<\/a><\/h3>\n","protected":false},"excerpt":{"rendered":"<p>Knapsack problem of Greedy method [ understand with real life example]. [fvplayer id=&#8221;284&#8243;] \ud83c\udf92 Knapsack Problem using Greedy Method \u2014 with Real-Life Example \u2705 What is the Knapsack Problem? It\u2019s a classic optimization problem where: You have a bag (knapsack) that can carry up to a certain weight\/capacity. You have items, each with a weight [&hellip;]<\/p>\n","protected":false},"author":66,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1640],"tags":[],"class_list":["post-3171","post","type-post","status-publish","format-standard","hentry","category-data-structure"],"_links":{"self":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/posts\/3171","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/users\/66"}],"replies":[{"embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/comments?post=3171"}],"version-history":[{"count":0,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/posts\/3171\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/media?parent=3171"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/categories?post=3171"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/tags?post=3171"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}