2645:. The total weight of a set of items is given by the total weight of the elements of the union of the corresponding element sets. The objective is to find a subset of the items with total weight not exceeding the knapsack capacity and maximal profit.
2100:
4794:
3879:
1029:
925:
4311:
5133:
Gens, G. V.; Levner, E. V. (1979). "Complexity and
Approximation Algorithms for Combinatorial Problems: A Survey". Central Economic and Mathematical Institute, Academy of Sciences of the USSR, Moscow.
1592:
3489:
4069:
2817:
1677:
4869:
3189:
2175:
1406:
724:
502:
234:
4972:
3745:
3647:
3537:
3292:
1776:
334:
1098:
568:
4165:
2732:
1331:
649:
427:
159:
4478:
4379:
3599:
3343:
3984:
3401:
3114:
86:
is used to select the item. The objective is to pick some of the items, with maximal total profit, while obeying that the maximum total weight of the chosen items must not exceed
4924:
4565:
3798:
3244:
2406:
2342:
1863:
1185:
777:
3697:
2227:
1458:
286:
4599:
4512:
4413:
4199:
4103:
2951:
2851:
2643:
2558:
2261:
1929:
1897:
1810:
1711:
1219:
1132:
63:
2889:
4632:
1252:
5104:
5054:
3044:
3015:
2982:
4668:
2916:
2605:
2520:
2453:
1500:
828:
1957:
2654:
If there is more than one constraint (for example, both a volume limit and a weight limit, where the volume and weight of each item are not related), we get the
2578:
2493:
2473:
2426:
2362:
2298:
4679:
2670:. (Note, "dimension" here does not refer to the shape of any items.) This has 0-1, bounded, and unbounded variants; the unbounded one is shown below.
3804:
5088:
3051:
1936:
As a special case of the multiple knapsack problem, when the profits are equal to weights and all bins have the same capacity, we can have
793:
938:
5242:
5165:
5038:
843:
4231:
1515:
3414:
3997:
2745:
1605:
5163:
Magazine, Michael J.; Chern, Maw-Sheng (1984). "A Note on
Approximation Schemes for Multidimensional Knapsack Problems".
4807:
3127:
2113:
1344:
662:
440:
172:
3062:
If all the profits are 1, we will try to maximize the number of items which would not exceed the knapsack capacity:
1944:
23:
4930:
3703:
3605:
3495:
3250:
1721:
292:
90:. Generally, these coefficients are scaled to become integers, and they are almost always assumed to be positive.
1041:
514:
4113:
26:, with many real-life applications. For this reason, many special cases and generalizations have been examined.
3896:, but since practical instances usually have far fewer types of items, another formulation is often used. Item
2679:
1278:
596:
374:
106:
4423:
4324:
3547:
3312:
5201:
3941:
3358:
3071:
3047:
3888:
5016:
4881:
4522:
3755:
3201:
2367:
2303:
1820:
1142:
736:
3657:
2187:
1418:
246:
5030:
5206:
4572:
4485:
4386:
4172:
4076:
3893:
3305:
2924:
2824:
2610:
2525:
2234:
1902:
1870:
1783:
1684:
1192:
1105:
36:
5098:
5048:
5020:
4218:
4212:
2861:
1261:
4604:
1224:
4670:, and we maximize the density of selected items which do not violate the capacity constraint:
4206:
If, to the multiple choice knapsack problem, we add the constraint that each subset is of size
5084:
5034:
4979:
Although less common than those above, several other knapsack-like problems exist, including:
3023:
2994:
2961:
5211:
5174:
2095:{\displaystyle \sum _{j=1}^{n}p_{j}x_{j}+\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}p_{ij}x_{i}x_{j}}
1266:
18:
4646:
2894:
2583:
2498:
2431:
1478:
806:
5080:
2563:
2478:
2458:
2411:
2347:
2283:
5236:
4789:{\displaystyle {\frac {\sum _{j=1}^{n}x_{j}p_{j}}{w_{0}+\sum _{j=1}^{n}x_{j}w_{j}}}}
5192:
Cohen, Reuven; Katzir, Liran (2008). "The
Generalized Maximum Coverage Problem".
3907:
times, each "pattern" of items which fit into a single knapsack have a variable,
5229:, D. Pisinger. Ph.D. thesis, DIKU, University of Copenhagen, Report 95/1 (1995).
2985:
789:
587:) does not put any upper bounds on the number of times an item may be selected:
3874:{\displaystyle \forall i\in \{1,\ldots ,n\}\wedge \forall j\in \{1,\ldots ,n\}}
5215:
3299:
If we have a number of containers (of the same size), and we wish to pack all
5024:
361:(which may be a positive integer, or infinity) on the number of times item
4996:
The last three of these are discussed in
Kellerer et al's reference work,
5178:
5226:
346:
One common variant is that each item can be chosen multiple times. The
1024:{\displaystyle \sum _{i=1}^{k}\sum _{j\in N_{i}}w_{ij}x_{ij}\leq W,}
796:(essentially the same as the one used in the 0-1 knapsack problem).
792:
in 1975 by Lueker. Both the bounded and unbounded variants admit an
830:, and exactly one item must be taken from each class, we get the
5075:
Kellerer, Hans and
Pferschy, Ulrich and Pisinger, David (2004).
1259:
If for each item the profit and weight are equal, we get the
920:{\displaystyle \sum _{i=1}^{k}\sum _{j\in N_{i}}p_{ij}x_{ij}}
2276:
SUKP is defined by
Kellerer et al (on page 423) as follows:
5120:
Two NP-complete problems in nonnegative integer programming
5026:
Knapsack
Problems: Algorithms and Computer Implementations
4306:{\displaystyle \sum _{i=1}^{k}\sum _{j=1}^{n}p_{ij}x_{ij}}
5122:. Report No. 178, Computer Science Laboratory, Princeton.
2988:
around 1980 and more strongly, has no FPTAS unless P=NP.
1587:{\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}p_{j}x_{ij}}
3050:
algorithm (similar to the one for basic knapsack) and a
4210:
and remove the restriction on total weight, we get the
3484:{\displaystyle \sum _{j=1}^{n}w_{j}x_{ij}\leq Wy_{i},}
4933:
4884:
4810:
4682:
4649:
4607:
4575:
4525:
4488:
4426:
4389:
4327:
4234:
4175:
4116:
4079:
4064:{\displaystyle \sum _{i=1}^{m}b_{ij}x_{i}\geq B_{j},}
4000:
3944:
3807:
3758:
3706:
3660:
3608:
3550:
3498:
3417:
3361:
3315:
3253:
3204:
3130:
3074:
3026:
2997:
2964:
2927:
2897:
2864:
2827:
2812:{\displaystyle \sum _{j=1}^{n}w_{ij}x_{j}\leq W_{i},}
2748:
2682:
2613:
2586:
2566:
2528:
2501:
2481:
2461:
2434:
2414:
2370:
2350:
2306:
2286:
2237:
2190:
2116:
1960:
1905:
1873:
1823:
1786:
1724:
1687:
1672:{\displaystyle \sum _{j=1}^{n}w_{j}x_{ij}\leq W_{i},}
1608:
1518:
1481:
1421:
1347:
1281:
1227:
1195:
1145:
1108:
1044:
941:
846:
809:
739:
665:
599:
517:
443:
377:
295:
249:
175:
109:
39:
3303:items in as few containers as possible, we get the
5144:"On the Existence of Fast Approximation Schemes".
4966:
4918:
4863:
4788:
4662:
4626:
4593:
4559:
4506:
4472:
4407:
4373:
4305:
4193:
4159:
4097:
4063:
3978:
3873:
3792:
3739:
3691:
3641:
3593:
3531:
3483:
3395:
3337:
3309:, which is modelled by having indicator variables
3286:
3238:
3183:
3108:
3038:
3009:
2991:The bounded and unbounded variants (for any fixed
2976:
2945:
2910:
2883:
2845:
2811:
2726:
2637:
2599:
2572:
2552:
2514:
2487:
2467:
2447:
2420:
2400:
2356:
2336:
2292:
2255:
2221:
2169:
2094:
1923:
1891:
1857:
1804:
1770:
1705:
1671:
1586:
1494:
1452:
1400:
1325:
1246:
1213:
1179:
1126:
1092:
1023:
919:
822:
771:
718:
643:
562:
496:
421:
328:
280:
228:
153:
57:
4216:, which is also the problem of finding a maximal
4864:{\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}
3184:{\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}
2170:{\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}
1401:{\displaystyle \sum _{j=1}^{n}p_{j}x_{j}\leq W,}
719:{\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}
497:{\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}
229:{\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}
8:
5103:: CS1 maint: multiple names: authors list (
5053:: CS1 maint: multiple names: authors list (
4967:{\displaystyle \forall j\in \{1,\ldots ,n\}}
4961:
4943:
4910:
4898:
4554:
4542:
4154:
4130:
3868:
3850:
3835:
3817:
3787:
3775:
3740:{\displaystyle \forall i\in \{1,\ldots ,n\}}
3734:
3716:
3686:
3674:
3642:{\displaystyle \forall j\in \{1,\ldots ,n\}}
3636:
3618:
3532:{\displaystyle \forall i\in \{1,\ldots ,n\}}
3526:
3508:
3287:{\displaystyle \forall j\in \{1,\ldots ,n\}}
3281:
3263:
3230:
3218:
2395:
2377:
2331:
2313:
2216:
2204:
1852:
1840:
1771:{\displaystyle \sum _{i=1}^{m}x_{ij}\leq 1,}
1447:
1435:
1174:
1162:
329:{\displaystyle \forall j\in \{1,\ldots ,n\}}
323:
305:
275:
263:
1093:{\displaystyle \sum _{j\in N_{i}}x_{ij}=1,}
563:{\displaystyle 0\leq x_{j}\leq u_{j},x_{j}}
4160:{\displaystyle x_{i}\in \{0,1,\ldots ,n\}}
5205:
4932:
4889:
4883:
4846:
4836:
4826:
4815:
4809:
4777:
4767:
4757:
4746:
4733:
4721:
4711:
4701:
4690:
4683:
4681:
4654:
4648:
4618:
4606:
4574:
4530:
4524:
4487:
4452:
4442:
4431:
4425:
4388:
4353:
4343:
4332:
4326:
4294:
4281:
4271:
4260:
4250:
4239:
4233:
4174:
4121:
4115:
4078:
4052:
4039:
4026:
4016:
4005:
3999:
3970:
3960:
3949:
3943:
3806:
3763:
3757:
3705:
3665:
3659:
3607:
3576:
3566:
3555:
3549:
3497:
3472:
3453:
3443:
3433:
3422:
3416:
3387:
3377:
3366:
3360:
3320:
3314:
3252:
3209:
3203:
3166:
3156:
3146:
3135:
3129:
3100:
3090:
3079:
3073:
3025:
2996:
2963:
2926:
2902:
2896:
2869:
2863:
2826:
2800:
2787:
2774:
2764:
2753:
2747:
2727:{\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}
2718:
2708:
2698:
2687:
2681:
2612:
2591:
2585:
2565:
2527:
2506:
2500:
2480:
2460:
2439:
2433:
2413:
2369:
2349:
2305:
2285:
2236:
2195:
2189:
2152:
2142:
2132:
2121:
2115:
2086:
2076:
2063:
2053:
2036:
2020:
2009:
1996:
1986:
1976:
1965:
1959:
1904:
1872:
1828:
1822:
1785:
1750:
1740:
1729:
1723:
1686:
1660:
1644:
1634:
1624:
1613:
1607:
1575:
1565:
1555:
1544:
1534:
1523:
1517:
1486:
1480:
1426:
1420:
1383:
1373:
1363:
1352:
1346:
1326:{\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}
1317:
1307:
1297:
1286:
1280:
1238:
1226:
1194:
1150:
1144:
1107:
1072:
1060:
1049:
1043:
1003:
990:
978:
967:
957:
946:
940:
908:
895:
883:
872:
862:
851:
845:
814:
808:
763:
744:
738:
701:
691:
681:
670:
664:
644:{\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}
635:
625:
615:
604:
598:
554:
541:
528:
516:
479:
469:
459:
448:
442:
422:{\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}
413:
403:
393:
382:
376:
294:
254:
248:
211:
201:
191:
180:
174:
154:{\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}
145:
135:
125:
114:
108:
38:
5070:
5068:
5066:
5064:
4473:{\displaystyle \sum _{j=1}^{n}x_{ij}=1,}
4374:{\displaystyle \sum _{i=1}^{n}x_{ij}=1,}
5008:
3594:{\displaystyle \sum _{i=1}^{n}x_{ij}=1}
3338:{\displaystyle y_{i}=1\Leftrightarrow }
22:is one of the most studied problems in
5096:
5046:
788:The unbounded variant was shown to be
2656:multiple-constrained knapsack problem
7:
3979:{\displaystyle \sum _{i=1}^{m}x_{i}}
3396:{\displaystyle \sum _{i=1}^{n}y_{i}}
3109:{\displaystyle \sum _{j=1}^{n}x_{j}}
29:Common to all versions are a set of
4992:Inverse-parametric knapsack problem
4643:variant there is an initial weight
5227:"Algorithms for Knapsack Problems"
5166:Mathematics of Operations Research
4934:
3841:
3808:
3707:
3609:
3499:
3254:
3017:) also exhibit the same hardness.
296:
14:
4919:{\displaystyle x_{j}\in \{0,1\},}
4560:{\displaystyle x_{ij}\in \{0,1\}}
3793:{\displaystyle x_{ij}\in \{0,1\}}
3239:{\displaystyle x_{j}\in \{0,1\},}
2660:multidimensional knapsack problem
2401:{\displaystyle P=\{1,\ldots ,m\}}
2337:{\displaystyle N=\{1,\ldots ,n\}}
1858:{\displaystyle x_{ij}\in \{0,1\}}
1180:{\displaystyle x_{ij}\in \{0,1\}}
799:If the items are subdivided into
772:{\displaystyle x_{j}\geq 0,x_{j}}
3692:{\displaystyle y_{i}\in \{0,1\}}
2222:{\displaystyle x_{j}\in \{0,1\}}
1453:{\displaystyle x_{j}\in \{0,1\}}
832:multiple-choice knapsack problem
281:{\displaystyle x_{j}\in \{0,1\}}
2958:The 0-1 variant (for any fixed
79:. The binary decision variable
5194:Information Processing Letters
3332:
1:
4594:{\displaystyle 1\leq i\leq k}
4507:{\displaystyle 1\leq i\leq n}
4408:{\displaystyle 1\leq j\leq n}
4194:{\displaystyle 1\leq i\leq m}
4098:{\displaystyle 1\leq j\leq n}
2946:{\displaystyle 1\leq j\leq n}
2846:{\displaystyle 1\leq i\leq m}
2638:{\displaystyle i=1,\ldots ,m}
2553:{\displaystyle j=1,\ldots ,n}
2256:{\displaystyle 1\leq j\leq n}
1924:{\displaystyle 1\leq i\leq m}
1892:{\displaystyle 1\leq j\leq n}
1805:{\displaystyle 1\leq j\leq n}
1706:{\displaystyle 1\leq i\leq m}
1214:{\displaystyle 1\leq i\leq k}
1127:{\displaystyle 1\leq i\leq k}
58:{\displaystyle 1\leq j\leq n}
3046:, these problems do admit a
2668:dimensional knapsack problem
65:having an associated profit
4986:Collapsing knapsack problem
2884:{\displaystyle x_{j}\geq 0}
1938:multiple subset sum problem
5259:
5243:Combinatorial optimization
4989:Nonlinear knapsack problem
4627:{\displaystyle j\in N_{i}}
2580:have non-negative weights
2495:have non-negative profits
2271:Set-Union Knapsack Problem
1945:Quadratic knapsack problem
1475:knapsacks with capacities
1247:{\displaystyle j\in N_{i}}
581:unbounded knapsack problem
24:combinatorial optimization
5216:10.1016/j.ipl.2008.03.017
4675:
4227:
3937:
3354:
3067:
2675:
1953:
1511:
1504:multiple knapsack problem
1274:
1265:(often the corresponding
839:
592:
370:
350:specifies, for each item
102:
4641:Maximum Density Knapsack
2428:corresponds to a subset
585:integer knapsack problem
348:bounded knapsack problem
97:in its most basic form:
4983:Nested knapsack problem
3918:patterns), and pattern
3039:{\displaystyle m\geq 2}
3010:{\displaystyle m\geq 2}
2977:{\displaystyle m\geq 2}
4968:
4920:
4865:
4831:
4790:
4762:
4706:
4664:
4628:
4595:
4561:
4508:
4474:
4447:
4409:
4375:
4348:
4307:
4276:
4255:
4195:
4161:
4099:
4065:
4021:
3980:
3965:
3875:
3794:
3741:
3693:
3643:
3595:
3571:
3533:
3485:
3438:
3397:
3382:
3339:
3288:
3240:
3185:
3151:
3110:
3095:
3058:Knapsack-like problems
3048:pseudo-polynomial time
3040:
3011:
2978:
2947:
2912:
2885:
2847:
2813:
2769:
2728:
2703:
2647:
2639:
2601:
2574:
2554:
2516:
2489:
2469:
2449:
2422:
2402:
2358:
2338:
2294:
2257:
2223:
2171:
2137:
2096:
2058:
2031:
1981:
1925:
1893:
1859:
1806:
1772:
1745:
1707:
1673:
1629:
1588:
1560:
1539:
1496:
1454:
1402:
1368:
1327:
1302:
1248:
1215:
1181:
1128:
1094:
1025:
962:
921:
867:
824:
773:
720:
686:
645:
620:
583:(sometimes called the
564:
498:
464:
423:
398:
342:Direct generalizations
330:
282:
230:
196:
155:
130:
59:
33:items, with each item
5146:Nonlinear Programming
5118:Lueker, G.S. (1975).
5031:John Wiley & Sons
4969:
4921:
4866:
4811:
4791:
4742:
4686:
4665:
4663:{\displaystyle w_{0}}
4629:
4596:
4562:
4509:
4475:
4427:
4410:
4376:
4328:
4308:
4256:
4235:
4196:
4162:
4100:
4066:
4001:
3981:
3945:
3889:cutting stock problem
3876:
3795:
3742:
3694:
3644:
3596:
3551:
3534:
3486:
3418:
3398:
3362:
3340:
3289:
3241:
3186:
3131:
3111:
3075:
3041:
3012:
2979:
2948:
2913:
2911:{\displaystyle x_{j}}
2886:
2848:
2814:
2749:
2729:
2683:
2640:
2602:
2600:{\displaystyle w_{i}}
2575:
2555:
2517:
2515:{\displaystyle p_{j}}
2490:
2470:
2450:
2448:{\displaystyle P_{j}}
2423:
2403:
2359:
2339:
2295:
2278:
2258:
2224:
2172:
2117:
2097:
2032:
2005:
1961:
1926:
1894:
1860:
1807:
1773:
1725:
1708:
1674:
1609:
1589:
1540:
1519:
1497:
1495:{\displaystyle W_{i}}
1455:
1403:
1348:
1328:
1282:
1249:
1216:
1182:
1129:
1095:
1026:
942:
922:
847:
825:
823:{\displaystyle N_{i}}
774:
721:
666:
646:
600:
565:
499:
444:
424:
378:
331:
283:
231:
176:
156:
110:
60:
5179:10.1287/moor.9.2.244
4931:
4882:
4808:
4680:
4647:
4605:
4573:
4523:
4486:
4424:
4387:
4325:
4232:
4173:
4114:
4077:
3998:
3942:
3892:is identical to the
3805:
3756:
3704:
3658:
3606:
3548:
3496:
3415:
3359:
3313:
3251:
3202:
3128:
3072:
3024:
2995:
2962:
2925:
2895:
2862:
2825:
2746:
2680:
2650:Multiple constraints
2611:
2584:
2564:
2526:
2499:
2479:
2459:
2432:
2412:
2368:
2348:
2304:
2284:
2235:
2188:
2114:
1958:
1903:
1871:
1821:
1784:
1722:
1685:
1606:
1516:
1479:
1419:
1345:
1279:
1225:
1193:
1143:
1106:
1042:
939:
844:
807:
737:
663:
597:
515:
441:
375:
293:
247:
173:
107:
37:
3894:bin packing problem
3306:bin packing problem
2560:, and the elements
2455:of the element set
2364:so-called elements
1269:is given instead):
4964:
4916:
4861:
4786:
4660:
4624:
4591:
4557:
4504:
4470:
4405:
4371:
4303:
4219:bipartite matching
4213:assignment problem
4191:
4157:
4095:
4061:
3976:
3871:
3790:
3737:
3689:
3639:
3591:
3529:
3481:
3393:
3335:
3284:
3236:
3181:
3106:
3036:
3007:
2984:) was shown to be
2974:
2943:
2908:
2881:
2843:
2809:
2724:
2635:
2597:
2570:
2550:
2512:
2485:
2465:
2445:
2418:
2398:
2354:
2334:
2290:
2253:
2219:
2167:
2092:
1921:
1889:
1855:
1802:
1768:
1703:
1669:
1584:
1492:
1450:
1398:
1323:
1262:subset sum problem
1244:
1211:
1177:
1124:
1090:
1067:
1021:
985:
917:
890:
820:
769:
716:
641:
560:
494:
419:
326:
278:
226:
151:
55:
5090:978-3-540-40286-2
5077:Knapsack Problems
5017:Martello, Silvano
4998:Knapsack Problems
4977:
4976:
4784:
4637:
4636:
4204:
4203:
3884:
3883:
3297:
3296:
2956:
2955:
2573:{\displaystyle i}
2488:{\displaystyle j}
2468:{\displaystyle P}
2421:{\displaystyle j}
2357:{\displaystyle m}
2293:{\displaystyle n}
2268:
2267:
1934:
1933:
1465:
1464:
1257:
1256:
1045:
963:
868:
786:
785:
779:integral for all
577:
576:
570:integral for all
365:can be selected:
354:, an upper bound
339:
338:
5250:
5220:
5219:
5209:
5189:
5183:
5182:
5160:
5154:
5153:
5152:: 415–437. 1980.
5141:
5135:
5134:
5130:
5124:
5123:
5115:
5109:
5108:
5102:
5094:
5072:
5059:
5058:
5052:
5044:
5013:
4973:
4971:
4970:
4965:
4925:
4923:
4922:
4917:
4894:
4893:
4870:
4868:
4867:
4862:
4851:
4850:
4841:
4840:
4830:
4825:
4795:
4793:
4792:
4787:
4785:
4783:
4782:
4781:
4772:
4771:
4761:
4756:
4738:
4737:
4727:
4726:
4725:
4716:
4715:
4705:
4700:
4684:
4673:
4672:
4669:
4667:
4666:
4661:
4659:
4658:
4633:
4631:
4630:
4625:
4623:
4622:
4600:
4598:
4597:
4592:
4566:
4564:
4563:
4558:
4538:
4537:
4513:
4511:
4510:
4505:
4479:
4477:
4476:
4471:
4460:
4459:
4446:
4441:
4414:
4412:
4411:
4406:
4380:
4378:
4377:
4372:
4361:
4360:
4347:
4342:
4312:
4310:
4309:
4304:
4302:
4301:
4289:
4288:
4275:
4270:
4254:
4249:
4225:
4224:
4200:
4198:
4197:
4192:
4166:
4164:
4163:
4158:
4126:
4125:
4104:
4102:
4101:
4096:
4070:
4068:
4067:
4062:
4057:
4056:
4044:
4043:
4034:
4033:
4020:
4015:
3985:
3983:
3982:
3977:
3975:
3974:
3964:
3959:
3935:
3934:
3880:
3878:
3877:
3872:
3799:
3797:
3796:
3791:
3771:
3770:
3746:
3744:
3743:
3738:
3698:
3696:
3695:
3690:
3670:
3669:
3648:
3646:
3645:
3640:
3600:
3598:
3597:
3592:
3584:
3583:
3570:
3565:
3538:
3536:
3535:
3530:
3490:
3488:
3487:
3482:
3477:
3476:
3461:
3460:
3448:
3447:
3437:
3432:
3402:
3400:
3399:
3394:
3392:
3391:
3381:
3376:
3352:
3351:
3344:
3342:
3341:
3336:
3325:
3324:
3293:
3291:
3290:
3285:
3245:
3243:
3242:
3237:
3214:
3213:
3190:
3188:
3187:
3182:
3171:
3170:
3161:
3160:
3150:
3145:
3115:
3113:
3112:
3107:
3105:
3104:
3094:
3089:
3065:
3064:
3045:
3043:
3042:
3037:
3016:
3014:
3013:
3008:
2983:
2981:
2980:
2975:
2952:
2950:
2949:
2944:
2917:
2915:
2914:
2909:
2907:
2906:
2890:
2888:
2887:
2882:
2874:
2873:
2852:
2850:
2849:
2844:
2818:
2816:
2815:
2810:
2805:
2804:
2792:
2791:
2782:
2781:
2768:
2763:
2733:
2731:
2730:
2725:
2723:
2722:
2713:
2712:
2702:
2697:
2673:
2672:
2644:
2642:
2641:
2636:
2606:
2604:
2603:
2598:
2596:
2595:
2579:
2577:
2576:
2571:
2559:
2557:
2556:
2551:
2521:
2519:
2518:
2513:
2511:
2510:
2494:
2492:
2491:
2486:
2474:
2472:
2471:
2466:
2454:
2452:
2451:
2446:
2444:
2443:
2427:
2425:
2424:
2419:
2407:
2405:
2404:
2399:
2363:
2361:
2360:
2355:
2343:
2341:
2340:
2335:
2299:
2297:
2296:
2291:
2262:
2260:
2259:
2254:
2228:
2226:
2225:
2220:
2200:
2199:
2176:
2174:
2173:
2168:
2157:
2156:
2147:
2146:
2136:
2131:
2101:
2099:
2098:
2093:
2091:
2090:
2081:
2080:
2071:
2070:
2057:
2052:
2030:
2019:
2001:
2000:
1991:
1990:
1980:
1975:
1951:
1950:
1930:
1928:
1927:
1922:
1898:
1896:
1895:
1890:
1864:
1862:
1861:
1856:
1836:
1835:
1811:
1809:
1808:
1803:
1777:
1775:
1774:
1769:
1758:
1757:
1744:
1739:
1712:
1710:
1709:
1704:
1678:
1676:
1675:
1670:
1665:
1664:
1652:
1651:
1639:
1638:
1628:
1623:
1593:
1591:
1590:
1585:
1583:
1582:
1570:
1569:
1559:
1554:
1538:
1533:
1509:
1508:
1501:
1499:
1498:
1493:
1491:
1490:
1459:
1457:
1456:
1451:
1431:
1430:
1407:
1405:
1404:
1399:
1388:
1387:
1378:
1377:
1367:
1362:
1332:
1330:
1329:
1324:
1322:
1321:
1312:
1311:
1301:
1296:
1272:
1271:
1267:decision problem
1253:
1251:
1250:
1245:
1243:
1242:
1220:
1218:
1217:
1212:
1186:
1184:
1183:
1178:
1158:
1157:
1133:
1131:
1130:
1125:
1099:
1097:
1096:
1091:
1080:
1079:
1066:
1065:
1064:
1030:
1028:
1027:
1022:
1011:
1010:
998:
997:
984:
983:
982:
961:
956:
926:
924:
923:
918:
916:
915:
903:
902:
889:
888:
887:
866:
861:
837:
836:
829:
827:
826:
821:
819:
818:
803:classes denoted
778:
776:
775:
770:
768:
767:
749:
748:
725:
723:
722:
717:
706:
705:
696:
695:
685:
680:
650:
648:
647:
642:
640:
639:
630:
629:
619:
614:
590:
589:
569:
567:
566:
561:
559:
558:
546:
545:
533:
532:
503:
501:
500:
495:
484:
483:
474:
473:
463:
458:
428:
426:
425:
420:
418:
417:
408:
407:
397:
392:
368:
367:
335:
333:
332:
327:
287:
285:
284:
279:
259:
258:
235:
233:
232:
227:
216:
215:
206:
205:
195:
190:
160:
158:
157:
152:
150:
149:
140:
139:
129:
124:
100:
99:
95:knapsack problem
64:
62:
61:
56:
19:knapsack problem
5258:
5257:
5253:
5252:
5251:
5249:
5248:
5247:
5233:
5232:
5223:
5207:10.1.1.156.2073
5191:
5190:
5186:
5162:
5161:
5157:
5143:
5142:
5138:
5132:
5131:
5127:
5117:
5116:
5112:
5095:
5091:
5081:Springer Verlag
5074:
5073:
5062:
5045:
5041:
5015:
5014:
5010:
5006:
4929:
4928:
4885:
4880:
4879:
4842:
4832:
4806:
4805:
4773:
4763:
4729:
4728:
4717:
4707:
4685:
4678:
4677:
4650:
4645:
4644:
4614:
4603:
4602:
4571:
4570:
4526:
4521:
4520:
4484:
4483:
4448:
4422:
4421:
4385:
4384:
4349:
4323:
4322:
4290:
4277:
4230:
4229:
4171:
4170:
4117:
4112:
4111:
4075:
4074:
4048:
4035:
4022:
3996:
3995:
3966:
3940:
3939:
3930:
3912:
3905:
3803:
3802:
3759:
3754:
3753:
3702:
3701:
3661:
3656:
3655:
3604:
3603:
3572:
3546:
3545:
3494:
3493:
3468:
3449:
3439:
3413:
3412:
3383:
3357:
3356:
3349:is being used:
3316:
3311:
3310:
3249:
3248:
3205:
3200:
3199:
3162:
3152:
3126:
3125:
3096:
3070:
3069:
3060:
3022:
3021:
2993:
2992:
2960:
2959:
2923:
2922:
2898:
2893:
2892:
2865:
2860:
2859:
2823:
2822:
2796:
2783:
2770:
2744:
2743:
2714:
2704:
2678:
2677:
2652:
2609:
2608:
2587:
2582:
2581:
2562:
2561:
2524:
2523:
2502:
2497:
2496:
2477:
2476:
2457:
2456:
2435:
2430:
2429:
2410:
2409:
2366:
2365:
2346:
2345:
2302:
2301:
2282:
2281:
2280:Given a set of
2233:
2232:
2191:
2186:
2185:
2148:
2138:
2112:
2111:
2082:
2072:
2059:
1992:
1982:
1956:
1955:
1901:
1900:
1869:
1868:
1824:
1819:
1818:
1782:
1781:
1746:
1720:
1719:
1683:
1682:
1656:
1640:
1630:
1604:
1603:
1571:
1561:
1514:
1513:
1482:
1477:
1476:
1422:
1417:
1416:
1379:
1369:
1343:
1342:
1313:
1303:
1277:
1276:
1234:
1223:
1222:
1191:
1190:
1146:
1141:
1140:
1104:
1103:
1068:
1056:
1040:
1039:
999:
986:
974:
937:
936:
904:
891:
879:
842:
841:
810:
805:
804:
759:
740:
735:
734:
697:
687:
661:
660:
631:
621:
595:
594:
550:
537:
524:
513:
512:
475:
465:
439:
438:
409:
399:
373:
372:
359:
344:
291:
290:
250:
245:
244:
207:
197:
171:
170:
141:
131:
105:
104:
84:
77:
70:
35:
34:
12:
11:
5:
5256:
5254:
5246:
5245:
5235:
5234:
5231:
5230:
5222:
5221:
5184:
5173:(2): 244–247.
5155:
5136:
5125:
5110:
5089:
5060:
5040:978-0471924203
5039:
5007:
5005:
5002:
4994:
4993:
4990:
4987:
4984:
4975:
4974:
4963:
4960:
4957:
4954:
4951:
4948:
4945:
4942:
4939:
4936:
4926:
4915:
4912:
4909:
4906:
4903:
4900:
4897:
4892:
4888:
4877:
4874:
4873:
4871:
4860:
4857:
4854:
4849:
4845:
4839:
4835:
4829:
4824:
4821:
4818:
4814:
4803:
4799:
4798:
4796:
4780:
4776:
4770:
4766:
4760:
4755:
4752:
4749:
4745:
4741:
4736:
4732:
4724:
4720:
4714:
4710:
4704:
4699:
4696:
4693:
4689:
4657:
4653:
4635:
4634:
4621:
4617:
4613:
4610:
4590:
4587:
4584:
4581:
4578:
4567:
4556:
4553:
4550:
4547:
4544:
4541:
4536:
4533:
4529:
4518:
4515:
4514:
4503:
4500:
4497:
4494:
4491:
4480:
4469:
4466:
4463:
4458:
4455:
4451:
4445:
4440:
4437:
4434:
4430:
4419:
4416:
4415:
4404:
4401:
4398:
4395:
4392:
4381:
4370:
4367:
4364:
4359:
4356:
4352:
4346:
4341:
4338:
4335:
4331:
4320:
4316:
4315:
4313:
4300:
4297:
4293:
4287:
4284:
4280:
4274:
4269:
4266:
4263:
4259:
4253:
4248:
4245:
4242:
4238:
4202:
4201:
4190:
4187:
4184:
4181:
4178:
4167:
4156:
4153:
4150:
4147:
4144:
4141:
4138:
4135:
4132:
4129:
4124:
4120:
4109:
4106:
4105:
4094:
4091:
4088:
4085:
4082:
4071:
4060:
4055:
4051:
4047:
4042:
4038:
4032:
4029:
4025:
4019:
4014:
4011:
4008:
4004:
3993:
3989:
3988:
3986:
3973:
3969:
3963:
3958:
3955:
3952:
3948:
3928:
3910:
3903:
3882:
3881:
3870:
3867:
3864:
3861:
3858:
3855:
3852:
3849:
3846:
3843:
3840:
3837:
3834:
3831:
3828:
3825:
3822:
3819:
3816:
3813:
3810:
3800:
3789:
3786:
3783:
3780:
3777:
3774:
3769:
3766:
3762:
3751:
3748:
3747:
3736:
3733:
3730:
3727:
3724:
3721:
3718:
3715:
3712:
3709:
3699:
3688:
3685:
3682:
3679:
3676:
3673:
3668:
3664:
3653:
3650:
3649:
3638:
3635:
3632:
3629:
3626:
3623:
3620:
3617:
3614:
3611:
3601:
3590:
3587:
3582:
3579:
3575:
3569:
3564:
3561:
3558:
3554:
3543:
3540:
3539:
3528:
3525:
3522:
3519:
3516:
3513:
3510:
3507:
3504:
3501:
3491:
3480:
3475:
3471:
3467:
3464:
3459:
3456:
3452:
3446:
3442:
3436:
3431:
3428:
3425:
3421:
3410:
3406:
3405:
3403:
3390:
3386:
3380:
3375:
3372:
3369:
3365:
3334:
3331:
3328:
3323:
3319:
3295:
3294:
3283:
3280:
3277:
3274:
3271:
3268:
3265:
3262:
3259:
3256:
3246:
3235:
3232:
3229:
3226:
3223:
3220:
3217:
3212:
3208:
3197:
3194:
3193:
3191:
3180:
3177:
3174:
3169:
3165:
3159:
3155:
3149:
3144:
3141:
3138:
3134:
3123:
3119:
3118:
3116:
3103:
3099:
3093:
3088:
3085:
3082:
3078:
3059:
3056:
3035:
3032:
3029:
3020:For any fixed
3006:
3003:
3000:
2973:
2970:
2967:
2954:
2953:
2942:
2939:
2936:
2933:
2930:
2919:
2905:
2901:
2880:
2877:
2872:
2868:
2857:
2854:
2853:
2842:
2839:
2836:
2833:
2830:
2819:
2808:
2803:
2799:
2795:
2790:
2786:
2780:
2777:
2773:
2767:
2762:
2759:
2756:
2752:
2741:
2737:
2736:
2734:
2721:
2717:
2711:
2707:
2701:
2696:
2693:
2690:
2686:
2651:
2648:
2634:
2631:
2628:
2625:
2622:
2619:
2616:
2594:
2590:
2569:
2549:
2546:
2543:
2540:
2537:
2534:
2531:
2509:
2505:
2484:
2464:
2442:
2438:
2417:
2397:
2394:
2391:
2388:
2385:
2382:
2379:
2376:
2373:
2353:
2333:
2330:
2327:
2324:
2321:
2318:
2315:
2312:
2309:
2289:
2266:
2265:
2263:
2252:
2249:
2246:
2243:
2240:
2229:
2218:
2215:
2212:
2209:
2206:
2203:
2198:
2194:
2183:
2180:
2179:
2177:
2166:
2163:
2160:
2155:
2151:
2145:
2141:
2135:
2130:
2127:
2124:
2120:
2109:
2105:
2104:
2102:
2089:
2085:
2079:
2075:
2069:
2066:
2062:
2056:
2051:
2048:
2045:
2042:
2039:
2035:
2029:
2026:
2023:
2018:
2015:
2012:
2008:
2004:
1999:
1995:
1989:
1985:
1979:
1974:
1971:
1968:
1964:
1932:
1931:
1920:
1917:
1914:
1911:
1908:
1888:
1885:
1882:
1879:
1876:
1865:
1854:
1851:
1848:
1845:
1842:
1839:
1834:
1831:
1827:
1816:
1813:
1812:
1801:
1798:
1795:
1792:
1789:
1778:
1767:
1764:
1761:
1756:
1753:
1749:
1743:
1738:
1735:
1732:
1728:
1717:
1714:
1713:
1702:
1699:
1696:
1693:
1690:
1679:
1668:
1663:
1659:
1655:
1650:
1647:
1643:
1637:
1633:
1627:
1622:
1619:
1616:
1612:
1601:
1597:
1596:
1594:
1581:
1578:
1574:
1568:
1564:
1558:
1553:
1550:
1547:
1543:
1537:
1532:
1529:
1526:
1522:
1489:
1485:
1463:
1462:
1460:
1449:
1446:
1443:
1440:
1437:
1434:
1429:
1425:
1414:
1411:
1410:
1408:
1397:
1394:
1391:
1386:
1382:
1376:
1372:
1366:
1361:
1358:
1355:
1351:
1340:
1336:
1335:
1333:
1320:
1316:
1310:
1306:
1300:
1295:
1292:
1289:
1285:
1255:
1254:
1241:
1237:
1233:
1230:
1210:
1207:
1204:
1201:
1198:
1187:
1176:
1173:
1170:
1167:
1164:
1161:
1156:
1153:
1149:
1138:
1135:
1134:
1123:
1120:
1117:
1114:
1111:
1100:
1089:
1086:
1083:
1078:
1075:
1071:
1063:
1059:
1055:
1052:
1048:
1037:
1034:
1033:
1031:
1020:
1017:
1014:
1009:
1006:
1002:
996:
993:
989:
981:
977:
973:
970:
966:
960:
955:
952:
949:
945:
934:
930:
929:
927:
914:
911:
907:
901:
898:
894:
886:
882:
878:
875:
871:
865:
860:
857:
854:
850:
817:
813:
784:
783:
766:
762:
758:
755:
752:
747:
743:
732:
729:
728:
726:
715:
712:
709:
704:
700:
694:
690:
684:
679:
676:
673:
669:
658:
654:
653:
651:
638:
634:
628:
624:
618:
613:
610:
607:
603:
575:
574:
557:
553:
549:
544:
540:
536:
531:
527:
523:
520:
510:
507:
506:
504:
493:
490:
487:
482:
478:
472:
468:
462:
457:
454:
451:
447:
436:
432:
431:
429:
416:
412:
406:
402:
396:
391:
388:
385:
381:
357:
343:
340:
337:
336:
325:
322:
319:
316:
313:
310:
307:
304:
301:
298:
288:
277:
274:
271:
268:
265:
262:
257:
253:
242:
239:
238:
236:
225:
222:
219:
214:
210:
204:
200:
194:
189:
186:
183:
179:
168:
164:
163:
161:
148:
144:
138:
134:
128:
123:
120:
117:
113:
82:
75:
68:
54:
51:
48:
45:
42:
13:
10:
9:
6:
4:
3:
2:
5255:
5244:
5241:
5240:
5238:
5228:
5225:
5224:
5217:
5213:
5208:
5203:
5199:
5195:
5188:
5185:
5180:
5176:
5172:
5168:
5167:
5159:
5156:
5151:
5147:
5140:
5137:
5129:
5126:
5121:
5114:
5111:
5106:
5100:
5092:
5086:
5082:
5078:
5071:
5069:
5067:
5065:
5061:
5056:
5050:
5042:
5036:
5032:
5028:
5027:
5022:
5018:
5012:
5009:
5003:
5001:
4999:
4991:
4988:
4985:
4982:
4981:
4980:
4958:
4955:
4952:
4949:
4946:
4940:
4937:
4927:
4913:
4907:
4904:
4901:
4895:
4890:
4886:
4878:
4876:
4875:
4872:
4858:
4855:
4852:
4847:
4843:
4837:
4833:
4827:
4822:
4819:
4816:
4812:
4804:
4801:
4800:
4797:
4778:
4774:
4768:
4764:
4758:
4753:
4750:
4747:
4743:
4739:
4734:
4730:
4722:
4718:
4712:
4708:
4702:
4697:
4694:
4691:
4687:
4674:
4671:
4655:
4651:
4642:
4619:
4615:
4611:
4608:
4588:
4585:
4582:
4579:
4576:
4568:
4551:
4548:
4545:
4539:
4534:
4531:
4527:
4519:
4517:
4516:
4501:
4498:
4495:
4492:
4489:
4481:
4467:
4464:
4461:
4456:
4453:
4449:
4443:
4438:
4435:
4432:
4428:
4420:
4418:
4417:
4402:
4399:
4396:
4393:
4390:
4382:
4368:
4365:
4362:
4357:
4354:
4350:
4344:
4339:
4336:
4333:
4329:
4321:
4318:
4317:
4314:
4298:
4295:
4291:
4285:
4282:
4278:
4272:
4267:
4264:
4261:
4257:
4251:
4246:
4243:
4240:
4236:
4226:
4223:
4221:
4220:
4215:
4214:
4209:
4188:
4185:
4182:
4179:
4176:
4168:
4151:
4148:
4145:
4142:
4139:
4136:
4133:
4127:
4122:
4118:
4110:
4108:
4107:
4092:
4089:
4086:
4083:
4080:
4072:
4058:
4053:
4049:
4045:
4040:
4036:
4030:
4027:
4023:
4017:
4012:
4009:
4006:
4002:
3994:
3991:
3990:
3987:
3971:
3967:
3961:
3956:
3953:
3950:
3946:
3936:
3933:
3931:
3925:
3921:
3917:
3913:
3906:
3899:
3895:
3891:
3890:
3865:
3862:
3859:
3856:
3853:
3847:
3844:
3838:
3832:
3829:
3826:
3823:
3820:
3814:
3811:
3801:
3784:
3781:
3778:
3772:
3767:
3764:
3760:
3752:
3750:
3749:
3731:
3728:
3725:
3722:
3719:
3713:
3710:
3700:
3683:
3680:
3677:
3671:
3666:
3662:
3654:
3652:
3651:
3633:
3630:
3627:
3624:
3621:
3615:
3612:
3602:
3588:
3585:
3580:
3577:
3573:
3567:
3562:
3559:
3556:
3552:
3544:
3542:
3541:
3523:
3520:
3517:
3514:
3511:
3505:
3502:
3492:
3478:
3473:
3469:
3465:
3462:
3457:
3454:
3450:
3444:
3440:
3434:
3429:
3426:
3423:
3419:
3411:
3408:
3407:
3404:
3388:
3384:
3378:
3373:
3370:
3367:
3363:
3353:
3350:
3348:
3329:
3326:
3321:
3317:
3308:
3307:
3302:
3278:
3275:
3272:
3269:
3266:
3260:
3257:
3247:
3233:
3227:
3224:
3221:
3215:
3210:
3206:
3198:
3196:
3195:
3192:
3178:
3175:
3172:
3167:
3163:
3157:
3153:
3147:
3142:
3139:
3136:
3132:
3124:
3121:
3120:
3117:
3101:
3097:
3091:
3086:
3083:
3080:
3076:
3066:
3063:
3057:
3055:
3053:
3049:
3033:
3030:
3027:
3018:
3004:
3001:
2998:
2989:
2987:
2971:
2968:
2965:
2940:
2937:
2934:
2931:
2928:
2920:
2903:
2899:
2878:
2875:
2870:
2866:
2858:
2856:
2855:
2840:
2837:
2834:
2831:
2828:
2820:
2806:
2801:
2797:
2793:
2788:
2784:
2778:
2775:
2771:
2765:
2760:
2757:
2754:
2750:
2742:
2739:
2738:
2735:
2719:
2715:
2709:
2705:
2699:
2694:
2691:
2688:
2684:
2674:
2671:
2669:
2665:
2661:
2657:
2649:
2646:
2632:
2629:
2626:
2623:
2620:
2617:
2614:
2592:
2588:
2567:
2547:
2544:
2541:
2538:
2535:
2532:
2529:
2507:
2503:
2482:
2462:
2440:
2436:
2415:
2392:
2389:
2386:
2383:
2380:
2374:
2371:
2351:
2344:and a set of
2328:
2325:
2322:
2319:
2316:
2310:
2307:
2287:
2277:
2274:
2272:
2264:
2250:
2247:
2244:
2241:
2238:
2230:
2213:
2210:
2207:
2201:
2196:
2192:
2184:
2182:
2181:
2178:
2164:
2161:
2158:
2153:
2149:
2143:
2139:
2133:
2128:
2125:
2122:
2118:
2110:
2107:
2106:
2103:
2087:
2083:
2077:
2073:
2067:
2064:
2060:
2054:
2049:
2046:
2043:
2040:
2037:
2033:
2027:
2024:
2021:
2016:
2013:
2010:
2006:
2002:
1997:
1993:
1987:
1983:
1977:
1972:
1969:
1966:
1962:
1952:
1949:
1947:
1946:
1941:
1939:
1918:
1915:
1912:
1909:
1906:
1886:
1883:
1880:
1877:
1874:
1866:
1849:
1846:
1843:
1837:
1832:
1829:
1825:
1817:
1815:
1814:
1799:
1796:
1793:
1790:
1787:
1779:
1765:
1762:
1759:
1754:
1751:
1747:
1741:
1736:
1733:
1730:
1726:
1718:
1716:
1715:
1700:
1697:
1694:
1691:
1688:
1680:
1666:
1661:
1657:
1653:
1648:
1645:
1641:
1635:
1631:
1625:
1620:
1617:
1614:
1610:
1602:
1599:
1598:
1595:
1579:
1576:
1572:
1566:
1562:
1556:
1551:
1548:
1545:
1541:
1535:
1530:
1527:
1524:
1520:
1510:
1507:
1505:
1502:, we get the
1487:
1483:
1474:
1470:
1461:
1444:
1441:
1438:
1432:
1427:
1423:
1415:
1413:
1412:
1409:
1395:
1392:
1389:
1384:
1380:
1374:
1370:
1364:
1359:
1356:
1353:
1349:
1341:
1338:
1337:
1334:
1318:
1314:
1308:
1304:
1298:
1293:
1290:
1287:
1283:
1273:
1270:
1268:
1264:
1263:
1239:
1235:
1231:
1228:
1208:
1205:
1202:
1199:
1196:
1188:
1171:
1168:
1165:
1159:
1154:
1151:
1147:
1139:
1137:
1136:
1121:
1118:
1115:
1112:
1109:
1101:
1087:
1084:
1081:
1076:
1073:
1069:
1061:
1057:
1053:
1050:
1046:
1038:
1036:
1035:
1032:
1018:
1015:
1012:
1007:
1004:
1000:
994:
991:
987:
979:
975:
971:
968:
964:
958:
953:
950:
947:
943:
935:
932:
931:
928:
912:
909:
905:
899:
896:
892:
884:
880:
876:
873:
869:
863:
858:
855:
852:
848:
838:
835:
833:
815:
811:
802:
797:
795:
791:
782:
764:
760:
756:
753:
750:
745:
741:
733:
731:
730:
727:
713:
710:
707:
702:
698:
692:
688:
682:
677:
674:
671:
667:
659:
656:
655:
652:
636:
632:
626:
622:
616:
611:
608:
605:
601:
591:
588:
586:
582:
573:
555:
551:
547:
542:
538:
534:
529:
525:
521:
518:
511:
509:
508:
505:
491:
488:
485:
480:
476:
470:
466:
460:
455:
452:
449:
445:
437:
434:
433:
430:
414:
410:
404:
400:
394:
389:
386:
383:
379:
369:
366:
364:
360:
353:
349:
341:
320:
317:
314:
311:
308:
302:
299:
289:
272:
269:
266:
260:
255:
251:
243:
241:
240:
237:
223:
220:
217:
212:
208:
202:
198:
192:
187:
184:
181:
177:
169:
166:
165:
162:
146:
142:
136:
132:
126:
121:
118:
115:
111:
101:
98:
96:
91:
89:
85:
78:
71:
52:
49:
46:
43:
40:
32:
27:
25:
21:
20:
5197:
5193:
5187:
5170:
5164:
5158:
5149:
5145:
5139:
5128:
5119:
5113:
5076:
5025:
5011:
4997:
4995:
4978:
4640:
4638:
4217:
4211:
4207:
4205:
3926:
3923:
3919:
3915:
3908:
3901:
3897:
3887:
3885:
3346:
3304:
3300:
3298:
3061:
3019:
2990:
2957:
2667:
2663:
2659:
2655:
2653:
2475:. The items
2408:, each item
2279:
2275:
2270:
2269:
1943:
1942:
1937:
1935:
1503:
1472:
1468:
1466:
1260:
1258:
831:
800:
798:
787:
780:
584:
580:
578:
571:
362:
355:
351:
347:
345:
94:
92:
87:
80:
73:
66:
30:
28:
17:
15:
5021:Toth, Paolo
4802:subject to
4319:subject to
3992:subject to
3914:(there are
3409:subject to
3122:subject to
2986:NP-complete
2740:subject to
2108:subject to
1600:subject to
1467:If we have
1339:subject to
933:subject to
790:NP-complete
657:subject to
435:subject to
167:subject to
72:and weight
5004:References
3922:uses item
3900:is needed
3345:container
1471:items and
5202:CiteSeerX
5200:: 15–22.
5099:cite book
5049:cite book
4953:…
4941:∈
4935:∀
4896:∈
4853:≤
4813:∑
4744:∑
4688:∑
4676:maximize
4612:∈
4586:≤
4580:≤
4540:∈
4499:≤
4493:≤
4429:∑
4400:≤
4394:≤
4330:∑
4258:∑
4237:∑
4228:maximize
4186:≤
4180:≤
4146:…
4128:∈
4090:≤
4084:≤
4046:≥
4003:∑
3947:∑
3938:minimize
3860:…
3848:∈
3842:∀
3839:∧
3827:…
3815:∈
3809:∀
3773:∈
3726:…
3714:∈
3708:∀
3672:∈
3628:…
3616:∈
3610:∀
3553:∑
3518:…
3506:∈
3500:∀
3463:≤
3420:∑
3364:∑
3355:minimize
3333:⇔
3273:…
3261:∈
3255:∀
3216:∈
3173:≤
3133:∑
3077:∑
3068:maximize
3031:≥
3002:≥
2969:≥
2938:≤
2932:≤
2876:≥
2838:≤
2832:≤
2794:≤
2751:∑
2685:∑
2676:maximize
2627:…
2542:…
2387:…
2323:…
2248:≤
2242:≤
2202:∈
2159:≤
2119:∑
2034:∑
2025:−
2007:∑
1963:∑
1954:maximize
1916:≤
1910:≤
1884:≤
1878:≤
1838:∈
1797:≤
1791:≤
1760:≤
1727:∑
1698:≤
1692:≤
1654:≤
1611:∑
1542:∑
1521:∑
1512:maximize
1433:∈
1390:≤
1350:∑
1284:∑
1275:maximize
1232:∈
1206:≤
1200:≤
1160:∈
1119:≤
1113:≤
1054:∈
1047:∑
1013:≤
972:∈
965:∑
944:∑
877:∈
870:∑
849:∑
840:maximize
751:≥
708:≤
668:∑
602:∑
593:maximize
535:≤
522:≤
486:≤
446:∑
380:∑
371:maximize
315:…
303:∈
297:∀
261:∈
218:≤
178:∑
112:∑
103:maximize
50:≤
44:≤
5237:Category
5023:(1990).
4601:and all
4569:for all
4482:for all
4383:for all
4169:for all
4073:for all
2921:for all
2918:integer
2821:for all
2231:for all
1899:and all
1867:for all
1780:for all
1681:for all
1221:and all
1189:for all
1102:for all
4639:In the
3932:times:
5204:
5087:
5037:
2300:items
2662:, or
794:FPTAS
5105:link
5085:ISBN
5055:link
5035:ISBN
5019:and
3886:The
3052:PTAS
579:The
93:The
16:The
5212:doi
5198:108
5175:doi
5239::
5210:.
5196:.
5169:.
5148:.
5101:}}
5097:{{
5083:.
5079:.
5063:^
5051:}}
5047:{{
5033:.
5029:.
5000:.
4222::
3929:ij
3054:.
2891:,
2658:,
2607:,
2522:,
2273::
1948::
1940:.
1506::
834::
5218:.
5214::
5181:.
5177::
5171:9
5150:4
5107:)
5093:.
5057:)
5043:.
4962:}
4959:n
4956:,
4950:,
4947:1
4944:{
4938:j
4914:,
4911:}
4908:1
4905:,
4902:0
4899:{
4891:j
4887:x
4859:,
4856:W
4848:j
4844:x
4838:j
4834:w
4828:n
4823:1
4820:=
4817:j
4779:j
4775:w
4769:j
4765:x
4759:n
4754:1
4751:=
4748:j
4740:+
4735:0
4731:w
4723:j
4719:p
4713:j
4709:x
4703:n
4698:1
4695:=
4692:j
4656:0
4652:w
4620:i
4616:N
4609:j
4589:k
4583:i
4577:1
4555:}
4552:1
4549:,
4546:0
4543:{
4535:j
4532:i
4528:x
4502:n
4496:i
4490:1
4468:,
4465:1
4462:=
4457:j
4454:i
4450:x
4444:n
4439:1
4436:=
4433:j
4403:n
4397:j
4391:1
4369:,
4366:1
4363:=
4358:j
4355:i
4351:x
4345:n
4340:1
4337:=
4334:i
4299:j
4296:i
4292:x
4286:j
4283:i
4279:p
4273:n
4268:1
4265:=
4262:j
4252:k
4247:1
4244:=
4241:i
4208:n
4189:m
4183:i
4177:1
4155:}
4152:n
4149:,
4143:,
4140:1
4137:,
4134:0
4131:{
4123:i
4119:x
4093:n
4087:j
4081:1
4059:,
4054:j
4050:B
4041:i
4037:x
4031:j
4028:i
4024:b
4018:m
4013:1
4010:=
4007:i
3972:i
3968:x
3962:m
3957:1
3954:=
3951:i
3927:b
3924:j
3920:i
3916:m
3911:i
3909:x
3904:j
3902:B
3898:j
3869:}
3866:n
3863:,
3857:,
3854:1
3851:{
3845:j
3836:}
3833:n
3830:,
3824:,
3821:1
3818:{
3812:i
3788:}
3785:1
3782:,
3779:0
3776:{
3768:j
3765:i
3761:x
3735:}
3732:n
3729:,
3723:,
3720:1
3717:{
3711:i
3687:}
3684:1
3681:,
3678:0
3675:{
3667:i
3663:y
3637:}
3634:n
3631:,
3625:,
3622:1
3619:{
3613:j
3589:1
3586:=
3581:j
3578:i
3574:x
3568:n
3563:1
3560:=
3557:i
3527:}
3524:n
3521:,
3515:,
3512:1
3509:{
3503:i
3479:,
3474:i
3470:y
3466:W
3458:j
3455:i
3451:x
3445:j
3441:w
3435:n
3430:1
3427:=
3424:j
3389:i
3385:y
3379:n
3374:1
3371:=
3368:i
3347:i
3330:1
3327:=
3322:i
3318:y
3301:n
3282:}
3279:n
3276:,
3270:,
3267:1
3264:{
3258:j
3234:,
3231:}
3228:1
3225:,
3222:0
3219:{
3211:j
3207:x
3179:,
3176:W
3168:j
3164:x
3158:j
3154:w
3148:n
3143:1
3140:=
3137:j
3102:j
3098:x
3092:n
3087:1
3084:=
3081:j
3034:2
3028:m
3005:2
2999:m
2972:2
2966:m
2941:n
2935:j
2929:1
2904:j
2900:x
2879:0
2871:j
2867:x
2841:m
2835:i
2829:1
2807:,
2802:i
2798:W
2789:j
2785:x
2779:j
2776:i
2772:w
2766:n
2761:1
2758:=
2755:j
2720:j
2716:x
2710:j
2706:p
2700:n
2695:1
2692:=
2689:j
2666:-
2664:m
2633:m
2630:,
2624:,
2621:1
2618:=
2615:i
2593:i
2589:w
2568:i
2548:n
2545:,
2539:,
2536:1
2533:=
2530:j
2508:j
2504:p
2483:j
2463:P
2441:j
2437:P
2416:j
2396:}
2393:m
2390:,
2384:,
2381:1
2378:{
2375:=
2372:P
2352:m
2332:}
2329:n
2326:,
2320:,
2317:1
2314:{
2311:=
2308:N
2288:n
2251:n
2245:j
2239:1
2217:}
2214:1
2211:,
2208:0
2205:{
2197:j
2193:x
2165:,
2162:W
2154:j
2150:x
2144:j
2140:w
2134:n
2129:1
2126:=
2123:j
2088:j
2084:x
2078:i
2074:x
2068:j
2065:i
2061:p
2055:n
2050:1
2047:+
2044:i
2041:=
2038:j
2028:1
2022:n
2017:1
2014:=
2011:i
2003:+
1998:j
1994:x
1988:j
1984:p
1978:n
1973:1
1970:=
1967:j
1919:m
1913:i
1907:1
1887:n
1881:j
1875:1
1853:}
1850:1
1847:,
1844:0
1841:{
1833:j
1830:i
1826:x
1800:n
1794:j
1788:1
1766:,
1763:1
1755:j
1752:i
1748:x
1742:m
1737:1
1734:=
1731:i
1701:m
1695:i
1689:1
1667:,
1662:i
1658:W
1649:j
1646:i
1642:x
1636:j
1632:w
1626:n
1621:1
1618:=
1615:j
1580:j
1577:i
1573:x
1567:j
1563:p
1557:n
1552:1
1549:=
1546:j
1536:m
1531:1
1528:=
1525:i
1488:i
1484:W
1473:m
1469:n
1448:}
1445:1
1442:,
1439:0
1436:{
1428:j
1424:x
1396:,
1393:W
1385:j
1381:x
1375:j
1371:p
1365:n
1360:1
1357:=
1354:j
1319:j
1315:x
1309:j
1305:p
1299:n
1294:1
1291:=
1288:j
1240:i
1236:N
1229:j
1209:k
1203:i
1197:1
1175:}
1172:1
1169:,
1166:0
1163:{
1155:j
1152:i
1148:x
1122:k
1116:i
1110:1
1088:,
1085:1
1082:=
1077:j
1074:i
1070:x
1062:i
1058:N
1051:j
1019:,
1016:W
1008:j
1005:i
1001:x
995:j
992:i
988:w
980:i
976:N
969:j
959:k
954:1
951:=
948:i
913:j
910:i
906:x
900:j
897:i
893:p
885:i
881:N
874:j
864:k
859:1
856:=
853:i
816:i
812:N
801:k
781:j
765:j
761:x
757:,
754:0
746:j
742:x
714:,
711:W
703:j
699:x
693:j
689:w
683:n
678:1
675:=
672:j
637:j
633:x
627:j
623:p
617:n
612:1
609:=
606:j
572:j
556:j
552:x
548:,
543:j
539:u
530:j
526:x
519:0
492:,
489:W
481:j
477:x
471:j
467:w
461:n
456:1
453:=
450:j
415:j
411:x
405:j
401:p
395:n
390:1
387:=
384:j
363:j
358:j
356:u
352:j
324:}
321:n
318:,
312:,
309:1
306:{
300:j
276:}
273:1
270:,
267:0
264:{
256:j
252:x
224:,
221:W
213:j
209:x
203:j
199:w
193:n
188:1
185:=
182:j
147:j
143:x
137:j
133:p
127:n
122:1
119:=
116:j
88:W
83:j
81:x
76:j
74:w
69:j
67:p
53:n
47:j
41:1
31:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.