Statistics

Problem Statement for "KnapsackProblem"

Problem Statement

We have several items and a bag that can carry a maximum weight of C. The i-th element of x is the weight of the i-th item. Return the number of different sets of items you can carry in the bag. Two sets are considered different if there exists at least one item which is included in one set and not included in the other.

Definition

Class:
KnapsackProblem
Method:
numberOfWays
Parameters:
int[], int
Returns:
int
Method signature:
int numberOfWays(int[] x, int C)
(be sure your method is public)

Constraints

  • x will contain between 1 and 30 elements, inclusive.
  • Each element of x will between 1 and 10^9, inclusive.
  • C will between 0 and 10^9, inclusive.

Examples

  1. {1}

    1

    Returns: 2

    We can either take the item or not take it.

  2. {1}

    2

    Returns: 2

    Same as the first example

  3. {2, 2}

    1

    Returns: 1

    We cannot take any of the items.

  4. {1,1}

    2

    Returns: 4

    We can take both items, just the first item, just the second item, or no items.

  5. {1,1}

    1

    Returns: 3

    This is the same as the previous example, but with a lower capacity bag. We cannot take both items in this case.

  6. {1,2,3,4,5}

    0

    Returns: 1

  7. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    30

    Returns: 1073741824

    We can take any subset of the items.

  8. {900000000,87566543,53467171}

    141033714

    Returns: 4

  9. {90000000,87566543,53467171}

    141033714

    Returns: 5

  10. {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    1000000000

    Returns: 31

  11. {7625496,3922618,1904379,38844,8420625,335187}

    8408378

    Returns: 20

  12. {422954}

    0

    Returns: 1

  13. {9788745,6918189,9221700,3293904,9085734,1565064,6706826,1591525,3346731,8355118}

    36439667

    Returns: 734

  14. {1331836,1151709,4972262,3503428,2991272,3481212,2190423,1675239,9265651}

    9853977

    Returns: 113

  15. {5064955,2245587}

    0

    Returns: 1

  16. {4666882,809956,7973367,46464,6102894,8363621,5711869,7389573}

    22284734

    Returns: 154

  17. {8674336,5002050,9408677}

    0

    Returns: 1

  18. {8278288,6155643}

    6569936

    Returns: 2

  19. {5374273,1664037,1094067,4975971,3091051,9767230,7205154,6628057,9621041,3960184}

    28860146

    Returns: 602

  20. {62279,8055275,8802756,42538,8280057,6802166,7801741}

    25511826

    Returns: 104

  21. {938376,4671630,3129605,2725406,7012890,6345090,6697327}

    29196153

    Returns: 126

  22. {4842195,426589,888967,436397,5139369,4184147,6703905,7742496,7931740,1628790,8578937,674595,5922245,2221933,4464746,76654,3578467,1171875,8899251,1618111,3237079}

    32656122

    Returns: 526295

  23. {4516470,6785787,1854814,1710715,1123818,2771490,769799,6468979,217341,3124877,9479423,3972061,7468800,8843923,13001,6411986,4433481,1096364}

    3074253

    Returns: 62

  24. {7358710,675634,1492398,5984910,7291316,7026090,4400311}

    0

    Returns: 1

  25. {9672998,719634,8193091,1579073,3700990,3210056,5883493,365257,6392395,4453451,2123036,3763506,31981,8943854,6252375,3976178,4578822,6224232,1915917,5304867,9307900}

    103244365

    Returns: 2097152

  26. {4914007,410717,7234835,8637156,3588154,8023405,6130426,9437615,3822954,9114911,8550209,3096386}

    609599

    Returns: 2

  27. {4313272,6085198,92250,8883537,3637043,27433,8047428,4862469,6280024,646688,3347732,7076464,6127822,3166625,522659,1156289,1739331}

    9874460

    Returns: 1011

  28. {3666858,1189438,3583432,2849008,8682050,5148756,5818833,7219988,2078338,3023293,7392230,8950162,9091467,1112742,9357996,4411434,5159589,2731523,8088745,9711008,5373111,5184522,9151050,8016828,3726417,319158,6965854,9463373}

    42277317

    Returns: 3668522

  29. {6520133,7322734,7815670,2341941,5087890,4055323,8911977,6557460,5235259,3306230}

    32203910

    Returns: 659

  30. {9329251,5587688,4306340}

    23238280

    Returns: 8

  31. {622730392,622730392,207576797,207576797,622730392,164252683,207576798,458477709}

    622730392

    Returns: 20

  32. {6531,859,251,868,1138,741,395,223,4521,8313}

    11920

    Returns: 513

  33. {1393,24988,938}

    27319

    Returns: 8

  34. {11787242,33461988,32560243,169824544,250685594}

    498319611

    Returns: 32

  35. {222157482,774546346,996703828,996703828}

    996703828

    Returns: 6

  36. {948914951,948914951}

    948914951

    Returns: 3

  37. {9960,9959,9960,9960,9959,9959,9960}

    69717

    Returns: 128

  38. {141225849,1642959,282451698,121364750,106028088,141225849,53415901}

    282451698

    Returns: 34

  39. {24872858,24872857,24872857,24872858,24872858,53268597,71095691}

    124364288

    Returns: 65

  40. {41265,17371,46604,17371,7532,17370,11207,17371,9479,22879}

    69483

    Returns: 206

  41. {239298405,272808810}

    512107215

    Returns: 4

  42. {741,3097,3158,1721,18351,20030,638}

    23868

    Returns: 65

  43. {23435277,112993335,15972123,14851425,115715652,14974719,7552254,28745856,15176760,31541872,37664445,133631123,112993335,37664445,34785491,112993335,225986670,37664445,37664445,15590788,112993335,37664445,37664445}

    225986670

    Returns: 51712

  44. {21256,31884,21256,1867,2234,2410,21257,19050,34813,31885,3395}

    63769

    Returns: 418

  45. {136140122,163368146,272280245,816840733,136140123,816840733,136140122,816840733,163368146,136140122,163368147,136140122,816840733,163368147,136140122,272280244,272280244,163368147}

    816840733

    Returns: 1832

  46. {44218,5342,28169,8843,8844,14739,14740,10707,8844,14739,8844,8843}

    44218

    Returns: 365

  47. {701087856}

    701087856

    Returns: 2

  48. {840393897,840393897}

    840393897

    Returns: 3

  49. {12586948,33183379,41479224,121217644,41479224,55305631,33183379,33183379,33183379,142180,25864839,55305632,50983652,33183379,165916895,27779660,43188816,114933243,122728079,140052056,137995055,41479224,41479223,32112303,55305632}

    165916895

    Returns: 8625

  50. {143868347,143868347,277923521,143868347,441418214,143868347,143868347}

    719341735

    Returns: 65

  51. {134456194,134456194,76832111,168930706,537824776,76832110,537824776,76832111,179274925,76832111,76832111,76832111,537824776,76832111,86944534,179274925,76832110,76832111,179274926,76832111,134456194,76832111,324114039,76832111,90564894,278329176,126766203,76832111,76832111,134456194}

    537824776

    Returns: 76040

  52. {19306462,96244645,1720054,240611612,5457977,58855828,210329861,96244645,96244645,16395580,24109072,160407742,481223224,71894840,187575082,381002326,409328384,160407741,6346819,481223224,240611612,96244645,160407741,24057792,27289595,434888340,240611612,96244644,240611612,46334884}

    481223224

    Returns: 176045

  53. {175512888,97826276,234017185,234017184,25978539,100293079,351025777,68158669,62912973,702051553,234017185,453963181,702051553,234017184,185175399,702051553,351025776,100293079,175512889,234017184,100293079,138430191,175512888,100293079,100293079,100293079,100293079,371657878,234017184,175512888}

    702051553

    Returns: 37586

  54. {59318606,145234182,417349674,93066160,140738456,3639252,134621247,208674837,208674837,59621382,103003660,59621382,59621382,31210397,318261316,27855096,3082677,59621382,417349674,59621382,80465127,17665252,240905095,5192727,69397670,179841372,59621382,76271,15824133,59621382}

    417349674

    Returns: 685742

  55. {7439,27245,375,7439,44631,82,7438,7438,1114,6690,702,42054,7439,14877,2183,7438,69,7439,14877,4146,7438,1966,14877,1418,7438,7438,7439,28463,7439,17386}

    44631

    Returns: 1623779

  56. {142857143,142857143,142857143,166666666,142857143,166666667,142857143,142857143,142857142,142857143,142857143,1000000000,142857143,166666667,142857143,250000000,166666667,203542167,250000000,142857143,572417328,190553944,142857143,809446056,250000000,250000000,142857142,224040505,166666667,166666666}

    1000000000

    Returns: 220738

  57. {250000000,669435418,228158174,250000000,250000000,333333333,1000000000,250000000,84333935,250000000,250000000,333333334,1000000000,250000000,250000000,250000000,250000000,250000000,250000000,250000000,1000000000,250000000,250000000,333333333,500000000,500000000,250000000,1000000000,18072473,1000000000}

    1000000000

    Returns: 8763

  58. {200000000,200000000,695238468,166666666,200000000,200000000,200000000,32426667,200000000,333333333,69674181,333333333,500000000,200000000,1000000000,200000000,210282746,65894709,166666667,166666667,4375456,333333334,166666667,500000000,893523696,200000000,166666666,28584077,200000000,166666667}

    1000000000

    Returns: 206848

  59. {19713380,226541424,250000000,500000000,70650700,1000000000,546737799,54959589,86830443,355296857,60754368,84819089,137642524,105793240,522860510,1000000000,500000000,458291181,250000000,11257554,102853712,10101830,11964129,250000000,250000000,88517310,93248105,847215364,37996699,65954193}

    1000000000

    Returns: 1039467

  60. {165862927,200000000,40552954,142857143,142857143,846936126,92934141,907065859,333333334,200000000,142857143,333333333,69642059,333333333,23556813,1000000000,514471921,142857143,500000000,200000000,200000000,1000000000,138998528,142857142,142857143,142857143,200000000,83421815,500000000,116556857}

    1000000000

    Returns: 199247

  61. {24589771,7952079,13499807,24097078,22499985,9944436,20018525,16121028,8835522,15310452,7693603,15488770,18645032,21349120,12460708,19610243,15777480,9010810,7508933,19648968,17136515,10119572,3373334,24183395,18786241,4983918,26647786,12281105,26651017,21908449}

    476133682

    Returns: 1073741824

  62. {20047846,2239877,15575012,15076920,10542177,19979898,4472091,2665012,6821937,25723085,9106012,6559859,16653538,10874475,11865475,17404905,6968330,17438887,25455158,8651080,22790751,12289011,25094925,8009991,9941692,5834489,20972341,2755970,28362677,25406192}

    387216936

    Returns: 1073739778

  63. {12167080,826062,1651630,26939121,16266791,11754951,15566753,20249483,23043702,732352,10176313,9791467,23921648,25903749,15401570,4985003,4727075,15841205,19172236,6113105,15196945,10054977,19772841,26057428,9787745,245871,27110620,18605402,12494013,29371044}

    433928182

    Returns: 1073741824

  64. {2366581,3966028,27858208,1384564,8718001,4285790,18200678,9138617,5749635,2193107,9771509,27757432,13530428,9114963,27557260,15020181,14442006,14203296,19742644,6771451,21769572,25311185,21058923,8435590,5996739,16395205,17653906,8823238,17708005,27085772}

    412010514

    Returns: 1073741824

  65. {4379254,3006252,18782290,22946557,17675622,4028897,25959330,20510665,6509699,21653885,1946848,24951709,19968750,6076502,2407495,1937073,2407934,5274,25106284,5456834,12010846,9043317,9388504,17513669,20665805,7650865,12159836,23134005,25057658,16112685}

    333364753

    Returns: 1073433196

  66. {13094006,17721438,7968216,19815736,6282286,18571994,25993308,21802636,22518369,29029366,7087116,11599146,19012922,11794683,4514689,8310358,23828724,17325531,12201760,13393388,12735441,21193492,20532102,12688853,17974518,17161572,14150147,12227534,2220363,12732226}

    455481920

    Returns: 1073741824

  67. {22320547,3692222,18992711,23707208,22973783,18982301,7949607,14275368,27588558,24969538,6893374,17156538,24265564,1564163,18469606,14013271,21729325,18139508,22618943,22485180,17052612,25304239,25415311,27633073,19007335,11176412,11074944,5422008,21618241,28170877}

    508498494

    Returns: 1073741054

  68. {21983464,15387905,23028584,4515734,12467171,5590471,16129464,873885,5462818,2329858,17160199,25056421,22697289,10949586,22938040,25492270,28569632,13879239,29495224,3271326,24185746,16689817,5915427,8420429,1898974,8001237,24180544,17678697,17206724,7705229}

    390164485

    Returns: 1073697209

  69. {3578483,29221842,4555108,8548325,17223491,19592072,2221423,1861983,13828393,29926901,1873386,28269091,6739538,27116041,9180451,14669451,3312705,16132727,19642860,1661308,25471607,3987340,7850969,2196295,16795586,10310603,29071065,3848652,21373048,29739152}

    371512419

    Returns: 1073696506

  70. {1944607,10563110,14247048,15060422,11938056,13964909,10619642,11428400,8523444,24378465,8348026,28358588,13550350,24160404,25635659,22549876,15046922,22624943,9393574,354885,5366073,16276386,1809630,16498,9477190,11511492,22176817,26205194,10140789,23572570}

    393861769

    Returns: 1073740270

  71. {27063924,23259330,4596207,7290296,13617534,3203914,14060263,7213214,15490159,22786062,16374643,19808243,10030218,5672835,20605265,6884444,7991117,23366666,8362642,7011583,19405835,29400620,17603827,15730160,10683886,16924472,23454416,2581020,10534572,21002530}

    399193617

    Returns: 1073739275

  72. {13631494,14917622,24892054,5335952,21096293,16355276,18097210,24624706,11052347,17904992,18673452,3595691,29420537,7988157,235127,26809856,14728789,1099487,13767696,14328321,10220811,23305080,6996535,11638544,389129,12813661,13503777,22367233,28423734,19768646}

    411876072

    Returns: 1073736647

  73. {4431027,10804458,22288376,12300227,28884241,7033115,18046454,8057106,6808209,17504679,28919502,7455131,2991163,626756,24522468,13134030,10837265,5254626,1881362,13854502,394275,25839993,11680190,29844870,7646393,7950092,11343939,7596352,18461629,17732739}

    318720832

    Returns: 1072895586

  74. {18694172,13044796,3034215,2457861,9722543,21426466,8937249,6974041,21232325,23646249,1970559,26665757,23126733,8935028,6138766,13941638,9445485,14612165,8566559,324310,17464100,16719753,29000353,20404914,20996323,5058577,12120285,17932816,28523615,24211120}

    368019756

    Returns: 1073449283

  75. {7236838,16813217,25723848,15833263,23139664,3999778,20580940,18692023,3641425,14118854,4913941,20985799,14365388,28291208,27422412,28090371,28640794,13862029,23451562,3937591,20902270,26064186,17256427,17257663,25375766,8740849,20641574,9222247,2216277,13045791}

    460603948

    Returns: 1073736522

  76. {1535795,28678030,13375225,9589493,28369349,26424130,4117738,11025258,11403636,10254463,24793529,18655255,28053207,29621247,3811799,5013468,6747557,14376415,19929174,1048726,29720648,7567876,19275555,29445284,5006714,14356081,20620304,17627135,16586483,2937797}

    378543334

    Returns: 1072821010

  77. {23697548,25853962,19527860,23161270,26263318,4785506,25733744,19398728,6967445,4263088,11123232,23815115,18248498,19514228,9737184,12016256,27621239,29515606,21704642,5867693,717552,5735727,3337571,108559,25963164,22983767,3890174,29979637,14615167,18650407}

    454100698

    Returns: 1073739233

  78. {20554181,28896118,7878839,14722634,23873910,10399462,13527177,21386976,10936230,27588996,22477051,18513757,12899456,18805024,3855568,17396505,23281758,26892543,16629959,12485829,15019034,1152509,4110053,4208750,11958606,9524292,4778963,23588547,28183025,21889789}

    453826994

    Returns: 1073741477

  79. {19907309,11769025,3454571,3919223,17122432,6630986,6765873,19904704,21821414,8745370,4456037,4896467,19957855,29954430,10368594,17535466,22736155,2422620,26600748,11497937,22830706,24409632,18264243,1337025,2715008,11000296,3781644,26739887,17890332,11219039}

    410655028

    Returns: 1073741824

  80. {9541272,22115995,16000475,14877727,18191425,14878624,14134854,25513227,23087615,7540862,10171299,4934500,17547776,20582860,8542040,20217224,8718266,21145184,5328916,8929634,13884888,14497139,8273019,17079336,27726944,24776237,70676,9857137,2828736,28810489}

    369269168

    Returns: 1073472669

  81. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912 }

    1000000000

    Returns: 1000000001

  82. {262236772, 208042609, 800207362, 428428949, 47718728, 793958355, 543227091, 255063701, 245922717, 448084510, 841298076, 50803247, 489249763, 634882132, 437249775, 192858938, 769723075, 17244079, 451954759, 998335072, 962932682, 107998840, 117154510, 343955362, 434512596, 123907813, 495496906, 1000000000, 1000000000, 1000000000 }

    1000000000

    Returns: 5477

  83. {90000000, 90000001, 90000002, 90000003, 90000004, 90000005, 90000006, 90000007, 90000008, 90000009, 90000010, 90000011, 90000012, 90000013, 90000014, 90000015, 90000016, 90000017, 90000018, 90000019, 90000020, 90000021, 90000022, 90000023, 90000024, 90000025, 90000026, 90000027, 90000028, 90000029 }

    1000000000

    Returns: 107636402

  84. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    1000000000

    Returns: 31

  85. {3883338, 5317955, 9314655, 189912, 2343229, 63774, 217710, 10847538, 1850040, 3070592, 77648, 3668243, 1196460, 352026, 12750045, 18867058, 12299276, 9719523, 4814208, 33462, 2916417, 21746899, 13384008, 856152, 14486550, 4982238, 4342180, 9282588, 7764540, 4552876 }

    100000000

    Returns: 667607940

  86. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    15

    Returns: 614429672

  87. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1000000000 }

    1000000000

    Returns: 536870913

  88. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1000, 2000, 4000, 8000, 16000, 32000, 64000, 128000, 256000, 512000, 1000000, 2000000, 4000000, 8000000, 16000000, 32000000, 64000000, 128000000, 256000000, 512000000 }

    1000000000

    Returns: 1048551403

  89. {1000000000, 1000000000, 1000000000 }

    1000000000

    Returns: 4

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: