{"entities":{"Q1082265":{"pageid":1093017,"ns":120,"title":"Item:Q1082265","lastrevid":66697443,"modified":"2026-04-12T12:10:25Z","type":"item","id":"Q1082265","labels":{"en":{"language":"en","value":"On equivalent knapsack problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3972638"}},"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":"Q1082265$D741D020-13A9-4831-8166-0351A3E76112","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1132bb7448f9412d68f444bf8bb5420fc772a90e","datavalue":{"value":{"text":"On equivalent knapsack problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1082265$B4BA87A0-83E7-4C91-B77B-6054DE6316C0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1b543f3a1871f76a01e1cc9ecf922912a3b9566a","datavalue":{"value":"0602.90103","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082265$1495AA4E-6D73-4592-A5B0-A99A238B7036","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6628dec1b8e766d3103a38f0982e1bc616c6631e","datavalue":{"value":"10.1016/0166-218X(86)90030-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082265$8ACE7460-23D2-4372-9D0A-64BB9D3C3086","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83acb26c132edffe3503227fdedd09777c685939","datavalue":{"value":{"entity-type":"item","numeric-id":1060191,"id":"Q1060191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082265$A9BC390D-5886-4C8A-B246-2E5EBD5B4B95","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082265$B72EB307-87FA-4738-AA4E-61B246EF1F02","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1082265$54DEDC87-AE19-495F-B47C-5DAE640B68A6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3df6761a6321909e6d3023274b6dae0fea639103","datavalue":{"value":"By aggregating objective function and constraint of a knapsack problem max\\(\\{\\) c'x\\(|\\) a'x\\(\\leq b\\), \\(x\\geq 0\\) integral\\(\\}\\) an equivalent problem of the following form is obtained: Let \\(t=[c_ 1b/a_ 1]+1\\) and let \\(F(z)=\\min \\{(c+ta)'x|\\) c'x\\(\\equiv z mod t\\), \\(x\\geq 0\\), integral\\(\\}\\). Then z is an optimal value of the given problem if it is maximal subject to \\(0\\leq z<t\\) and \\(z+tb\\geq F(z)\\). Such a value z can be determined by dynamic programming with recursion: \\(F(z)=\\min_{j}(c_ j+ta_ j+F(z-c_ j))\\). This procedure can be speeded up by calculating a recursion only for the values \\(1,2,...,c_ 1-1\\). Since the classical recursions use computation modulo \\(a_ 1\\), the new method might be advantageous if \\(c_ 1<a_ 1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082265$B812B970-39CA-4138-935F-7ABBA6938B42","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4a45374906fa7445234d8f571198ca1750e8882a","datavalue":{"value":{"entity-type":"item","numeric-id":170644,"id":"Q170644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082265$027013A2-5932-40F4-BF71-9B8473A146F1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082265$361A09CF-48EE-4268-9DA1-1509EF7CD8B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082265$FBF6A703-E6C1-46EF-A23B-8099E2002624","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082265$1A2DB5ED-488A-4F3D-A62A-238A19D8D15C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5db2a4cfc9f51e81a5b673424c8a059455d5c385","datavalue":{"value":"3972638","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082265$51ABE002-4A8D-4C42-A34C-10EBF277DD01","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21edb9da1b3e981be8262133490e4b2133d749f6","datavalue":{"value":"corner polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082265$B2CA012E-964A-498D-BB66-C5D1AC766818","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a303e9f8182aef3f6a577f4ef7bdc9e82c77fabf","datavalue":{"value":"group knapsack","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082265$DC61E910-A31B-48E8-9C89-F4AD878A9C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61680cc9a5a92b77d12a6c8e0ee7a0f750dcd26e","datavalue":{"value":"aggregating objective function and constraint","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082265$EB9C87F8-7040-4252-A2F1-4A7D3F379FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd9f81e2de676ca1bc7efadeabffd39fb5463e86","datavalue":{"value":"knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082265$0658DC3F-3FFD-44F3-8170-CB8D27E03598","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":"Q1082265$6A767947-B0C9-4B57-A4B4-480D2EAF8F4F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"03f1ddaba8285217bb41a356c810dd9d4f0f25b5","datavalue":{"value":{"entity-type":"item","numeric-id":5595961,"id":"Q5595961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082265$36EB03D7-B49F-4712-A8C0-359A989BFBCC","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":"Q1082265$AB5F8120-373C-4C6B-AD6C-9B6B63C6ECBB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b38f6cdd28924998b6decf4f7604274c6cf014bd","datavalue":{"value":{"entity-type":"item","numeric-id":3028724,"id":"Q3028724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5730340336541c2eda4001cfccddc05721090135","datavalue":{"value":{"amount":"+0.8347223401069641","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":"Q1082265$43D387B4-8C11-460B-89CB-1D9736B3E1EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dce3afd090313db3bc782643b73926688ae47b43","datavalue":{"value":{"entity-type":"item","numeric-id":3321838,"id":"Q3321838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9068e0e24f9705341a86a65ad87bd166c528dc78","datavalue":{"value":{"amount":"+0.8286502957344055","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":"Q1082265$A2D1BFAB-A9E3-48AA-B7EF-71E9EFD18D80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37d8ddbecd4a13692af51232d1bc7f4cfe55f5e7","datavalue":{"value":{"entity-type":"item","numeric-id":3342214,"id":"Q3342214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1be1ba567fdcc58ef4e5387e0fa2a4542b23e79","datavalue":{"value":{"amount":"+0.8113168478012085","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":"Q1082265$68BFC53B-E5F6-42E3-9D66-0076467BF9EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fab6f177f3ea762ef271759c7f3ad821cfd0adf0","datavalue":{"value":{"entity-type":"item","numeric-id":3757684,"id":"Q3757684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf8959599575da0ab71410f4b03c6a1a54a659c8","datavalue":{"value":{"amount":"+0.8094275593757629","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":"Q1082265$30840677-5742-479B-9E2D-818086E26C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f52271aaf87fd750fca042a24e493840c8974131","datavalue":{"value":{"entity-type":"item","numeric-id":1270786,"id":"Q1270786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39ff5ab1523105fbadf28175009399fc2b454ab0","datavalue":{"value":{"amount":"+0.8090409636497498","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":"Q1082265$0ED7F87A-4EA4-4C07-9D1E-ADD04B26A86D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On equivalent knapsack problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_equivalent_knapsack_problems"}}}}}