{"payload":{"allShortcutsEnabled":false,"path":"src/algorithms/sets/knapsack-problem","repo":{"id":458013065,"defaultBranch":"master","name":"javascript-algorithms","ownerLogin":"ninefyi","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2022-02-11T02:02:31.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/276376?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1644544959.132894","canEdit":false,"refType":"branch","currentOid":"7a37a6b86e76ee22bf93ffd9d01d7acfd79d0714"},"tree":{"items":[{"name":"__test__","path":"src/algorithms/sets/knapsack-problem/__test__","contentType":"directory"},{"name":"Knapsack.js","path":"src/algorithms/sets/knapsack-problem/Knapsack.js","contentType":"file"},{"name":"KnapsackItem.js","path":"src/algorithms/sets/knapsack-problem/KnapsackItem.js","contentType":"file"},{"name":"README.md","path":"src/algorithms/sets/knapsack-problem/README.md","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.md","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eKnapsack Problem\u003c/h1\u003e\u003ca id=\"user-content-knapsack-problem\" class=\"anchor\" aria-label=\"Permalink: Knapsack Problem\" href=\"#knapsack-problem\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe knapsack problem or rucksack problem is a problem in\ncombinatorial optimization: Given a set of items, each with\na weight and a value, determine the number of each item to\ninclude in a collection so that the total weight is less\nthan or equal to a given limit and the total value is as\nlarge as possible.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIt derives its name from the problem faced by someone who is\nconstrained by a fixed-size knapsack and must fill it with the\nmost valuable items.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eExample of a one-dimensional (constraint) knapsack problem:\nwhich boxes should be chosen to maximize the amount of money\nwhile still keeping the overall weight under or equal to 15 kg?\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/85a05b33570b27ba61eb51cf6e543b0a4ba160e145cbf76dd20151e2620a436d/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f662f66642f4b6e61707361636b2e737667\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/85a05b33570b27ba61eb51cf6e543b0a4ba160e145cbf76dd20151e2620a436d/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f662f66642f4b6e61707361636b2e737667\" alt=\"knapsack problem\" data-canonical-src=\"https://upload.wikimedia.org/wikipedia/commons/f/fd/Knapsack.svg\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eDefinition\u003c/h2\u003e\u003ca id=\"user-content-definition\" class=\"anchor\" aria-label=\"Permalink: Definition\" href=\"#definition\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e0/1 knapsack problem\u003c/h3\u003e\u003ca id=\"user-content-01-knapsack-problem\" class=\"anchor\" aria-label=\"Permalink: 0/1 knapsack problem\" href=\"#01-knapsack-problem\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe most common problem being solved is the \u003cstrong\u003e0/1 knapsack problem\u003c/strong\u003e,\nwhich restricts the number \u003ccode\u003exi\u003c/code\u003e of copies of each kind of item to zero or one.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eGiven a set of n items numbered from \u003ccode\u003e1\u003c/code\u003e up to \u003ccode\u003en\u003c/code\u003e, each with a\nweight \u003ccode\u003ewi\u003c/code\u003e and a value \u003ccode\u003evi\u003c/code\u003e, along with a maximum weight\ncapacity \u003ccode\u003eW\u003c/code\u003e,\u003c/p\u003e\n\u003cp dir=\"auto\"\u003emaximize \u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/b1bae34e1ff127ec8e9bae75acb5042bd49fd7c6871e9e23cb0c432728ad9d14/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f38353632303033376433363864323133366662333336313730326466366134383934313639333162\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/b1bae34e1ff127ec8e9bae75acb5042bd49fd7c6871e9e23cb0c432728ad9d14/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f38353632303033376433363864323133366662333336313730326466366134383934313639333162\" alt=\"0/1 knapsack\" data-canonical-src=\"https://wikimedia.org/api/rest_v1/media/math/render/svg/85620037d368d2136fb3361702df6a489416931b\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003esubject to \u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/78efc96908be8748de83afe22ee9ee2750aa6e2e1459f71cf3be8a2f6f0ad9d4/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f64643665376339626361343339373938303937366561366431393233373530306365336238313736\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/78efc96908be8748de83afe22ee9ee2750aa6e2e1459f71cf3be8a2f6f0ad9d4/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f64643665376339626361343339373938303937366561366431393233373530306365336238313736\" alt=\"0/1 knapsack\" data-canonical-src=\"https://wikimedia.org/api/rest_v1/media/math/render/svg/dd6e7c9bca4397980976ea6d19237500ce3b8176\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\nand \u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/6701c2fc3368ebc78a2851064db784965bd4edfff4b5e08b2fc50ad41551fe1a/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f30376464613731646132613633303736326337623231623531656135346638366634323266393531\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/6701c2fc3368ebc78a2851064db784965bd4edfff4b5e08b2fc50ad41551fe1a/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f30376464613731646132613633303736326337623231623531656135346638366634323266393531\" alt=\"0/1 knapsack\" data-canonical-src=\"https://wikimedia.org/api/rest_v1/media/math/render/svg/07dda71da2a630762c7b21b51ea54f86f422f951\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere \u003ccode\u003exi\u003c/code\u003e represents the number of instances of item \u003ccode\u003ei\u003c/code\u003e to\ninclude in the knapsack. Informally, the problem is to maximize\nthe sum of the values of the items in the knapsack so that the\nsum of the weights is less than or equal to the knapsack's\ncapacity.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eBounded knapsack problem (BKP)\u003c/h3\u003e\u003ca id=\"user-content-bounded-knapsack-problem-bkp\" class=\"anchor\" aria-label=\"Permalink: Bounded knapsack problem (BKP)\" href=\"#bounded-knapsack-problem-bkp\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe \u003cstrong\u003ebounded knapsack problem (BKP)\u003c/strong\u003e removes the restriction\nthat there is only one of each item, but restricts the number\n\u003ccode\u003exi\u003c/code\u003e of copies of each kind of item to a maximum non-negative\ninteger value \u003ccode\u003ec\u003c/code\u003e:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003emaximize \u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/b1bae34e1ff127ec8e9bae75acb5042bd49fd7c6871e9e23cb0c432728ad9d14/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f38353632303033376433363864323133366662333336313730326466366134383934313639333162\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/b1bae34e1ff127ec8e9bae75acb5042bd49fd7c6871e9e23cb0c432728ad9d14/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f38353632303033376433363864323133366662333336313730326466366134383934313639333162\" alt=\"bounded knapsack\" data-canonical-src=\"https://wikimedia.org/api/rest_v1/media/math/render/svg/85620037d368d2136fb3361702df6a489416931b\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003esubject to \u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/78efc96908be8748de83afe22ee9ee2750aa6e2e1459f71cf3be8a2f6f0ad9d4/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f64643665376339626361343339373938303937366561366431393233373530306365336238313736\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/78efc96908be8748de83afe22ee9ee2750aa6e2e1459f71cf3be8a2f6f0ad9d4/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f64643665376339626361343339373938303937366561366431393233373530306365336238313736\" alt=\"bounded knapsack\" data-canonical-src=\"https://wikimedia.org/api/rest_v1/media/math/render/svg/dd6e7c9bca4397980976ea6d19237500ce3b8176\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\nand \u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/596d830789e3b0ab8450565bb1dda274e20ad8d16a5c599e99b08c082cbbe2d4/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f36633863356163346638323437623362386530316538396465373661316466306561393639383231\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/596d830789e3b0ab8450565bb1dda274e20ad8d16a5c599e99b08c082cbbe2d4/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f36633863356163346638323437623362386530316538396465373661316466306561393639383231\" alt=\"bounded knapsack\" data-canonical-src=\"https://wikimedia.org/api/rest_v1/media/math/render/svg/6c8c5ac4f8247b3b8e01e89de76a1df0ea969821\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eUnbounded knapsack problem (UKP)\u003c/h3\u003e\u003ca id=\"user-content-unbounded-knapsack-problem-ukp\" class=\"anchor\" aria-label=\"Permalink: Unbounded knapsack problem (UKP)\" href=\"#unbounded-knapsack-problem-ukp\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe \u003cstrong\u003eunbounded knapsack problem (UKP)\u003c/strong\u003e places no upper bound\non the number of copies of each kind of item and can be\nformulated as above except for that the only restriction\non \u003ccode\u003exi\u003c/code\u003e is that it is a non-negative integer.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003emaximize \u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/b1bae34e1ff127ec8e9bae75acb5042bd49fd7c6871e9e23cb0c432728ad9d14/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f38353632303033376433363864323133366662333336313730326466366134383934313639333162\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/b1bae34e1ff127ec8e9bae75acb5042bd49fd7c6871e9e23cb0c432728ad9d14/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f38353632303033376433363864323133366662333336313730326466366134383934313639333162\" alt=\"unbounded knapsack\" data-canonical-src=\"https://wikimedia.org/api/rest_v1/media/math/render/svg/85620037d368d2136fb3361702df6a489416931b\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003esubject to \u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/78efc96908be8748de83afe22ee9ee2750aa6e2e1459f71cf3be8a2f6f0ad9d4/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f64643665376339626361343339373938303937366561366431393233373530306365336238313736\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/78efc96908be8748de83afe22ee9ee2750aa6e2e1459f71cf3be8a2f6f0ad9d4/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f64643665376339626361343339373938303937366561366431393233373530306365336238313736\" alt=\"unbounded knapsack\" data-canonical-src=\"https://wikimedia.org/api/rest_v1/media/math/render/svg/dd6e7c9bca4397980976ea6d19237500ce3b8176\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\nand \u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/abfdd28bc1402e8f1500914bdd32dc7384056e1378c3d4929e90f0dbe2ec1672/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f39306139393731306636316435646561313965343961653562333131363464326235366230376533\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/abfdd28bc1402e8f1500914bdd32dc7384056e1378c3d4929e90f0dbe2ec1672/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f39306139393731306636316435646561313965343961653562333131363464326235366230376533\" alt=\"unbounded knapsack\" data-canonical-src=\"https://wikimedia.org/api/rest_v1/media/math/render/svg/90a99710f61d5dea19e49ae5b31164d2b56b07e3\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eReferences\u003c/h2\u003e\u003ca id=\"user-content-references\" class=\"anchor\" aria-label=\"Permalink: References\" href=\"#references\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003ca href=\"https://en.wikipedia.org/wiki/Knapsack_problem\" rel=\"nofollow\"\u003eWikipedia\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://www.youtube.com/watch?v=8LusJS5-AGo\u0026amp;list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8\" rel=\"nofollow\"\u003e0/1 Knapsack Problem on YouTube\u003c/a\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Knapsack Problem","anchor":"knapsack-problem","htmlText":"Knapsack Problem"},{"level":2,"text":"Definition","anchor":"definition","htmlText":"Definition"},{"level":3,"text":"0/1 knapsack problem","anchor":"01-knapsack-problem","htmlText":"0/1 knapsack problem"},{"level":3,"text":"Bounded knapsack problem (BKP)","anchor":"bounded-knapsack-problem-bkp","htmlText":"Bounded knapsack problem (BKP)"},{"level":3,"text":"Unbounded knapsack problem (UKP)","anchor":"unbounded-knapsack-problem-ukp","htmlText":"Unbounded knapsack problem (UKP)"},{"level":2,"text":"References","anchor":"references","htmlText":"References"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fninefyi%2Fjavascript-algorithms%2Ftree%2Fmaster%2Fsrc%2Falgorithms%2Fsets%2Fknapsack-problem"}},"totalCount":4,"showBranchInfobar":true},"fileTree":{"src/algorithms/sets":{"items":[{"name":"cartesian-product","path":"src/algorithms/sets/cartesian-product","contentType":"directory"},{"name":"combination-sum","path":"src/algorithms/sets/combination-sum","contentType":"directory"},{"name":"combinations","path":"src/algorithms/sets/combinations","contentType":"directory"},{"name":"fisher-yates","path":"src/algorithms/sets/fisher-yates","contentType":"directory"},{"name":"knapsack-problem","path":"src/algorithms/sets/knapsack-problem","contentType":"directory"},{"name":"longest-common-subsequence","path":"src/algorithms/sets/longest-common-subsequence","contentType":"directory"},{"name":"longest-increasing-subsequence","path":"src/algorithms/sets/longest-increasing-subsequence","contentType":"directory"},{"name":"maximum-subarray","path":"src/algorithms/sets/maximum-subarray","contentType":"directory"},{"name":"permutations","path":"src/algorithms/sets/permutations","contentType":"directory"},{"name":"power-set","path":"src/algorithms/sets/power-set","contentType":"directory"},{"name":"shortest-common-supersequence","path":"src/algorithms/sets/shortest-common-supersequence","contentType":"directory"}],"totalCount":11},"src/algorithms":{"items":[{"name":"cryptography","path":"src/algorithms/cryptography","contentType":"directory"},{"name":"graph","path":"src/algorithms/graph","contentType":"directory"},{"name":"image-processing","path":"src/algorithms/image-processing","contentType":"directory"},{"name":"linked-list","path":"src/algorithms/linked-list","contentType":"directory"},{"name":"math","path":"src/algorithms/math","contentType":"directory"},{"name":"ml","path":"src/algorithms/ml","contentType":"directory"},{"name":"search","path":"src/algorithms/search","contentType":"directory"},{"name":"sets","path":"src/algorithms/sets","contentType":"directory"},{"name":"sorting","path":"src/algorithms/sorting","contentType":"directory"},{"name":"statistics","path":"src/algorithms/statistics","contentType":"directory"},{"name":"string","path":"src/algorithms/string","contentType":"directory"},{"name":"tree","path":"src/algorithms/tree","contentType":"directory"},{"name":"uncategorized","path":"src/algorithms/uncategorized","contentType":"directory"}],"totalCount":13},"src":{"items":[{"name":"algorithms","path":"src/algorithms","contentType":"directory"},{"name":"data-structures","path":"src/data-structures","contentType":"directory"},{"name":"playground","path":"src/playground","contentType":"directory"},{"name":"utils","path":"src/utils","contentType":"directory"}],"totalCount":4},"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":".husky","path":".husky","contentType":"directory"},{"name":"assets","path":"assets","contentType":"directory"},{"name":"src","path":"src","contentType":"directory"},{"name":".babelrc","path":".babelrc","contentType":"file"},{"name":".editorconfig","path":".editorconfig","contentType":"file"},{"name":".eslintrc","path":".eslintrc","contentType":"file"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".npmrc","path":".npmrc","contentType":"file"},{"name":".nvmrc","path":".nvmrc","contentType":"file"},{"name":"BACKERS.md","path":"BACKERS.md","contentType":"file"},{"name":"CODE_OF_CONDUCT.md","path":"CODE_OF_CONDUCT.md","contentType":"file"},{"name":"CONTRIBUTING.md","path":"CONTRIBUTING.md","contentType":"file"},{"name":"LICENSE","path":"LICENSE","contentType":"file"},{"name":"README.ar-AR.md","path":"README.ar-AR.md","contentType":"file"},{"name":"README.de-DE.md","path":"README.de-DE.md","contentType":"file"},{"name":"README.es-ES.md","path":"README.es-ES.md","contentType":"file"},{"name":"README.fr-FR.md","path":"README.fr-FR.md","contentType":"file"},{"name":"README.id-ID.md","path":"README.id-ID.md","contentType":"file"},{"name":"README.it-IT.md","path":"README.it-IT.md","contentType":"file"},{"name":"README.ja-JP.md","path":"README.ja-JP.md","contentType":"file"},{"name":"README.ko-KR.md","path":"README.ko-KR.md","contentType":"file"},{"name":"README.md","path":"README.md","contentType":"file"},{"name":"README.pl-PL.md","path":"README.pl-PL.md","contentType":"file"},{"name":"README.pt-BR.md","path":"README.pt-BR.md","contentType":"file"},{"name":"README.ru-RU.md","path":"README.ru-RU.md","contentType":"file"},{"name":"README.tr-TR.md","path":"README.tr-TR.md","contentType":"file"},{"name":"README.uk-UA.md","path":"README.uk-UA.md","contentType":"file"},{"name":"README.vi-VN.md","path":"README.vi-VN.md","contentType":"file"},{"name":"README.zh-CN.md","path":"README.zh-CN.md","contentType":"file"},{"name":"README.zh-TW.md","path":"README.zh-TW.md","contentType":"file"},{"name":"jest.config.js","path":"jest.config.js","contentType":"file"},{"name":"package-lock.json","path":"package-lock.json","contentType":"file"},{"name":"package.json","path":"package.json","contentType":"file"}],"totalCount":34}},"fileTreeProcessingTime":18.785633,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/ninefyi/javascript-algorithms/branches":{"post":"ik6404YY6JPba-dwv8_WViMztLOgZfOKtezbpFZ7C6Q1Duv_E5KQiF9YJA_GYQBRLgXW1mYay-n1yw2UCKKR3w"},"/ninefyi/javascript-algorithms/branches/fetch_and_merge/master":{"post":"FFgDUK8rrwxtXmANaQU3OzpK6uvpFhrrIgz_5oisqr2qHPcotln_Mq_7G5h-UE56a92bJo1EQmUujbVV2NfFGQ"},"/ninefyi/javascript-algorithms/branches/fetch_and_merge/master?discard_changes=true":{"post":"sZoRUqfwi5X68d40q6taVP7VN7Py9aRztPNjGRNqOQkP3uUqvoLbqzhUpaG8_iMVr0JGfpan_P24cimqQxFWrQ"}}},"title":"javascript-algorithms/src/algorithms/sets/knapsack-problem at master · ninefyi/javascript-algorithms","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-b84e9496fc59.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}
You can’t perform that action at this time.