{"entities":{"Q1178644":{"pageid":1189393,"ns":120,"title":"Item:Q1178644","lastrevid":66436671,"modified":"2026-04-12T10:04:02Z","type":"item","id":"Q1178644","labels":{"en":{"language":"en","value":"An extension of a greedy heuristic for the knapsack problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 21986"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$0C3EC17B-F8F9-46C0-961F-B396DB399FFD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"856b218792e62f2443b9e6566d069ce25f915ed6","datavalue":{"value":{"text":"An extension of a greedy heuristic for the knapsack problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1178644$07E66AF7-18F8-43F4-94F0-2EC6FBFD8654","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7eed61297cdf67a3bab377efc4d834ce3ab8771b","datavalue":{"value":"0743.90082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178644$71DDF742-BB34-41D2-BEAA-858CC6990435","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3a5bb22ac5cef374a576f09096b81eda5d57e9a7","datavalue":{"value":"10.1016/0377-2217(91)90313-K","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178644$8144C950-57F5-4860-AADB-8B029274E31B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$8DDD3FE2-DA2E-4D1C-BF2B-638049148D47","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1178644$F11B2D1A-55C0-4147-A0BD-A550BBB60C52","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3f22a7f30c7b49bb8c636f7d966b4350445ad3a2","datavalue":{"value":"A new heuristic for the knapsack problem which may be formulated in the following way is analyzed: Find nonnegative integers \\(x_ 1,\\dots,x_ n\\) such that \\(a_ 1x_ 1+\\cdots+a_ nx_ n\\leq b\\) and \\(p_ 1x_ 1+\\cdots+p_ nx_ n\\) is maximized where \\(p_ 1/a_ 1\\geq p_ 2/a_ 2\\geq\\cdots\\geq p_ n/a_ n\\). This heuristic \\(H_ 2\\) gets the maximal value by allocating \\(b\\) only to activities 1, 2 with, perhaps, some residual. The residual is then allocated to activities 3, 4 in an optimal manner, leaving, perhaps, a residual, etc. It extends the well-known greedy heuristic \\(H_ 1\\) which first allocates activity 1 in an optimal way, then activity 2, etc. It is shown that neither one of these two heuristics dominates the other. Furthermore, the performance of \\(H_ 2\\) is analyzed and necessary and sufficient conditions for \\(H_ 2\\) to be optimal are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178644$2B0780B1-84EB-4EEA-853A-5BBCF79580AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178644$86CB92B9-A547-48EF-815D-EA17C1A38CBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178644$2266174C-D3A1-480E-A0F0-E73D9C63E492","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f0dff6d0fb1aefaa7d7329ea141a89868d8938c2","datavalue":{"value":"21986","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178644$7C7C3967-C5D8-4988-84C5-D1040D7C3D61","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f641bd239fe6f0d5fb2cc0d2b3f89cbc609bab87","datavalue":{"value":"heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178644$EF605286-89D8-4E47-944A-60C65D5A3158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd9f81e2de676ca1bc7efadeabffd39fb5463e86","datavalue":{"value":"knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178644$409B41D4-4283-482D-97E2-6A4C26AE8AD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd0ec47f2d4dab7908c2ebbe2726174dab4de56e","datavalue":{"value":"greedy heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178644$127D7FD2-E4B5-4808-907B-DD992DAB42B2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"14fb6158c2e7a30d22594a5ac8edc4708d1a10b2","datavalue":{"value":{"entity-type":"item","numeric-id":181183,"id":"Q181183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$DF79C09D-36D6-4767-9D77-95717F750730","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"647403b42bff8e5868a53244a891290fdc1b119f","datavalue":{"value":{"entity-type":"item","numeric-id":177705,"id":"Q177705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$C4A92F18-E76E-410C-A0BA-D1F4616279CE","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$7493A09E-5904-47D2-8D28-279899ED7A5C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$7391819A-6741-4F3E-AD71-3EACE64B4405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa74c0bb2c71d8d24f83c953c7f1811531f8473b","datavalue":{"value":{"entity-type":"item","numeric-id":3214706,"id":"Q3214706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$E41541A7-DFA8-4C6A-8B92-E4D10AF049AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f57cb52d5b46d9b84e5c5fdecf79231c1f4f0138","datavalue":{"value":{"entity-type":"item","numeric-id":4178782,"id":"Q4178782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$339E50E7-76D2-4E5B-AED7-7976E81B933A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a02e5846a8a2b23e50649c744d199c26a3ee1cc7","datavalue":{"value":{"entity-type":"item","numeric-id":5328572,"id":"Q5328572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$EEBE5D0F-7910-4755-A587-B7AD8EE49B87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93972e67b0d6609e6c386aa611c07ebcde847786","datavalue":{"value":{"entity-type":"item","numeric-id":4124599,"id":"Q4124599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$2A218408-75EC-419D-A8FF-6F949B2B0E0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eaf1022db4a42ecb807eebe5be57a911b60556e4","datavalue":{"value":{"entity-type":"item","numeric-id":4062195,"id":"Q4062195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$685627E7-BD0C-48C9-8685-A739296617B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba10f0323a51550871a590a908f6c28185d0eb5d","datavalue":{"value":{"entity-type":"item","numeric-id":3703584,"id":"Q3703584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$A169AE31-4E26-4278-B19D-68A669931C97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ceb1ba0723c9843d5b7426f9c2de143e52782040","datavalue":{"value":{"entity-type":"item","numeric-id":4062194,"id":"Q4062194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178644$A43754CD-B013-45EE-BC69-2CF4C493CF12","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3fd130e894b982e15c3ddeabb702449422b3100","datavalue":{"value":{"entity-type":"item","numeric-id":1200766,"id":"Q1200766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cabf500c306513a296049f9704485e4ef526ef16","datavalue":{"value":{"amount":"+0.87330561876297","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1178644$6DCB64CA-2FD9-4725-8108-A554F7F02BC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b65847e7c893b72999fe46dc8eb3010478fd449","datavalue":{"value":{"entity-type":"item","numeric-id":1203804,"id":"Q1203804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf3a270a597ac12682e2dca7d0dafac24e096aa2","datavalue":{"value":{"amount":"+0.8575789928436279","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1178644$71CD43B1-C9AE-40E8-AA41-E04731027FF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9456b53a9f6fadf921a10243d86b09e81126a98","datavalue":{"value":{"entity-type":"item","numeric-id":1803680,"id":"Q1803680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a086b9ee375546dd8d3f36d99d173d67cf2efc33","datavalue":{"value":{"amount":"+0.855103611946106","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1178644$ECE68DFF-02E2-49F4-8490-18A2EBA358FB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An extension of a greedy heuristic for the knapsack problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_extension_of_a_greedy_heuristic_for_the_knapsack_problem"}}}}}