Can't get right answer using knapsack solver for big weights

asked 2020-11-27 07:35:47 -0600

ZM.J gravatar image

Hi, everyone! I try to use knapsack solver in sage to solve subset-sum problem, but can't get right answer.

Here's my code:


w = [14458739583668313985335691344891472311875271693111382572228715284614280890246364802396417435556889337293549792771429664851526631243202599713002001204329623834692761556566103182854793429825366964697185613100200128534136253773591574323584829806615944449783148031166245509766964743905101376235221533004504596199924513319, 666478501102276345336129081046675889877823000126713828712521277354743631250651806859903255656490576566365094968335208685535988085675273148083064010878903884452847570574619144117757930661039703725836092329797988986881132654561468165937903233816033112341415274542471570237934746290148513046516186705539686839255683963, 12483395608227564401246139730582425030094495563771203448829211407956875481728459958100983000397978582119117141470853764626147156533719074753356484041549218050223933745068220362719604751496847322228393764977147651785878988178645316191437718832242875664792255663903585370355613270777696761655711166777808766901174542498, 3505207998224608424211680850477891155530670836245398616064451630462809993203957007179764112256747203052378376538933489506916476351178477110481587409940590602811766210000379477178602453921431696931207055433768636866138770281069482547162059577657381056396187445572696841190077944328073108886706870675930738543800676739, 12986283148600659617997284671935144696615783492915468417761170919667481529556719470615133907251379884686754007187125659053040526340972714132344079531164308887981065090023330010801222540755712117211808372133660526605032212019753607843173149761601206843641257330138812876195618129826181008843828044125458016252914672311]
enc = 14458739583668313985335691344891472311875271693111382572228715284614280890246364802396417435556889337293549792771429664851526631243202599713002001204329623834692761556566103182854793429825366964697185613100200128534136253773591574323584829806615944449783148031166245509766964743905101376235221533004504596199924513319
from sage.numerical.knapsack import knapsack
import pickle

print(enc)
print(type(enc))

sol = knapsack(zip(w,w), max=enc)

print(sol)

and it'll give an inf. (obviously, choosing the first element in w is the optimal solution)

Any help would be appreciated.

edit retag flag offensive close merge delete