Looping through two lists and randomly aggregating elements to equal an element from another list

Question

I have three datasets, "CV", "FV" and "LA". I have attached reproducible data for all of them. The idea is that some combination of the elements in each column of CV and FV should sum up to equal the corresponding column entry in LA. You can think of each row entry in each column as having two possible outcomes, either it equals the value in CV or it equals the value in FV.

My current method is a brute force one. I generate a dataframe df_bob, and fill it randomly with either an element from CV or FV. I then aggregate this list and check the difference between the corresponding element from LA. I save the iteration which has the smallest difference, in a list, l_finals. This list has the combination of elements which aggregate to get to (or as close as I can to) the corresponding LA element. And then a 1 or a 2 (1 if it is an element from CV and 2 if its an element from FV), for each column that is looped through.

It does the job if I set the number of iterations to a large number, but it takes ages (Three loops and the method is a purely random one). I was wondering if there was a way to perform this algorithm in a less brute force manner, therefore requiring less computing time?

Here is the code I am currently using:

library(caret)
library(readxl)
set.seed(411)

df_CV <-  data.frame(read_excel("CV.xlsx"))
df_FV <- data.frame(read_excel("FV.xlsx"))
df_LA <- data.frame(read_excel("LA.xlsx"))

l_dif<- c()
l_finals<- c()

for(k in 1:ncol(df_LA)){
  idifMin <- 1000000000

  for(j in 1:20000){

  df_bob <- data.frame(df_CV[,k],df_FV[,k])
  df_final <-data.frame(c())
    for(i in 1:nrow(df_bob)){
      r <- sample(1:2,1)
      df_final[i,1]<-df_bob[i,r]
      df_final[i,2]<-r
    }

  idif <- sum(df_final[,1])+df_LA[,k]
  l_dif <- cbind(l_dif, idif)
    if(abs(idif)<abs(idifMin)){
      idifMin<-idif
      df_best <- df_final
    }
  }
  l_finals <- cbind(l_finals, df_best[,1], df_best[,2])

}

Here is the data in text form:

CV:

   0    1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18
320446  558245  319873  803455  611428  596234  24215   794590  582109  736434  624491  451544  352170  889357  595392  736355  401609  613174  55810
289884  828164  228777  232580  744795  663188  182071  292221  483034  437606  420378  59116   852644  147417  997675  416773  394209  638738  111395
550053  87308   44398   784360  668998  652140  61818   971801  159877  191641  459370  654481  84116   126776  732596  109117  906246  789235  308060
513830  978509  385267  648434  968876  764889  123435  737553  431799  838237  200792  859764  61002   929356  749615  887816  989663  407719  423781
284001  165456  680800  925983  4228    593538  826030  60438   338471  427333  614914  864478  202555  264660  922667  996376  164456  757038  41524
216820  235518  959869  752077  968732  362814  926543  144529  114658  841491  897634  199295  502388  529615  113620  712583  217445  375363  187147
970890  804096  992217  316356  156105  388333  22646   305011  60412   823331  485435  164495  129206  428451  466283  988203  194960  554939  325926
399375  919320  783371  835515  310706  757646  496110  770644  401981  755272  649688  604984  61062   88031   757112  22391   129306  386872  98320
802181  779785  916936  278812  674808  675218  36786   858379  451237  832692  846785  762282  416091  414694  9497    778436  488397  64091   656841
185814  129921  564141  280941  267096  297380  981779  770693  356458  156537  897851  308764  863072  817394  730970  746977  707754  472978  954950
177836  52483   431814  436553  69959   917728  997649  146712  121617  639243  254264  630123  803449  737208  294175  318587  325157  746828  386573
755486  63142   93095   152267  147691  629833  875730  85543   297708  771018  32108   466473  94736   476150  163862  917604  648048  794561  424487
87840   283878  908415  122819  631551  446701  589510  975919  479002  923304  506093  947017  434895  603704  526757  870451  882471  698782  892288
512425  434573  978120  171493  856826  79529   137793  210719  366966  632885  729722  76110   997626  658932  129308  286892  860331  878534  91016
982957  99116   516112  482743  264943  279695  891486  971790  561111  309095  58460   2570    772052  643821  749670  871921  112301  736067  759193
868155  923438  615361  395822  938507  985002  377216  267788  467545  460758  684319  483415  620495  541584  893175  728675  320769  819886  964721
919125  699079  498845  484441  652977  402577  716249  240098  466653  374657  212141  969469  270420  780220  331123  873291  721255  373017  750047
728706  503429  215220  961123  622615  44144   710188  435457  872641  737635  224442  918631  822325  462575  698914  706752  285181  606355  149249
564834  391827  730930  519434  169706  850385  897398  720886  579479  656563  407658  510847  275319  97008   248914  204639  909146  699399  554974
796185  967337  913528  270931  112849  628608  987253  304417  941156  487738  467440  745556  70104   86071   344588  720157  616401  987281  168286
716983  234547  201438  816150  403313  126367  125333  458069  285574  765629  188019  127161  539861  162954  266894  362911  824277  342408  286639
757870  332563  478929  160129  336228  953594  832097  122727  451594  743378  286202  411519  849707  742254  478730  756942  824035  884802  480874
549164  18651   412165  608141  519700  238449  231695  788194  336208  706266  535697  980992  728326  913709  485445  569890  341405  261614  238784
298561  268305  274246  978909  578733  398048  318060  601890  404212  708631  626139  683565  492023  310107  482462  514620  298713  19482   234085
735895  885692  534791  943805  947282  434255  174084  290059  313607  324411  846567  264720  368204  627704  400863  232034  522764  830844  722255
62402   963921  604929  638554  932765  745714  3674    3155    872952  461165  272973  987795  88122   309458  667869  249983  5858    97592   654919
240528  329941  525987  462739  907254  997931  18072   322609  924250  170321  50014   583746  409207  129538  987190  721270  969110  285665  128325
822876  363262  966046  619320  285886  639508  62547   250782  282472  242169  197924  94951   102483  383397  314255  535479  261825  602068  770265
564417  651378  981389  398973  59407   520390  694047  392827  415138  952837  22319   797984  821901  335588  11113   371781  988420  645864  97539
484462  525551  729880  390995  108589  795275  332009  272572  747901  304679  89949   487863  258617  608016  131945  194957  323792  522714  116716
862922  64640   737913  943758  138025  700724  599252  280690  628719  699348  131500  981586  538477  601120  203836  79121   977685  409499  605985
464382  458084  950207  937222  982392  896130  189955  201275  813726  757086  335551  496921  254556  13020   677034  243001  611997  745279  439141
486004  771657  29590   311636  949255  178183  682477  184693  498034  478796  750617  144694  808598  911119  320403  287678  155397  462017  610196
542338  193970  641761  326487  769535  992676  72645   305463  367129  567730  481419  801079  757702  317532  258714  684985  878241  749836  965444
557606  128089  608609  299726  163102  732714  590357  760764  108804  694905  679673  965802  471091  730849  718673  818705  752045  574992  969673
724243  765106  992622  915109  5878    500440  451416  593776  801350  862788  346293  408942  746836  963678  176277  684284  166470  506039  69048
422007  400440  714317  253123  50252   574276  614477  770795  848794  790922  136601  297154  260342  735498  250444  254657  444987  693550  297673
355572  356939  520919  753175  827121  6487    689456  105840  968471  193314  789759  503568  725256  136616  226395  81951   884465  226582  710319
736649  458189  3547    104152  31104   999099  872656  365103  641860  992649  35064   970780  61495   892448  921526  201327  890856  20572   466523
647192  760844  362936  568677  855492  369064  788308  896806  809253  908882  236246  241009  651272  705953  504631  776435  242115  564729  811052
690159  96591   721702  597105  776002  824607  4393    69294   745585  760232  710240  976106  599840  843843  989611  194095  929863  257068  200316
870690  545208  790493  880531  986423  582213  199844  618766  32653   490120  71453   119617  328122  767466  700296  326958  472533  329592  678365
571276  447072  451463  947248  854832  440812  527390  598666  129901  929615  113757  394850  679019  798242  186512  249937  575797  389922  26287
393786  371085  817072  205319  775901  26866   533685  769063  242550  778544  389141  625382  874117  738516  39404   274983  34997   896976  469675
575987  397470  616140  99125   252347  398168  331558  782761  70088   3706    792742  760695  124705  47828   255914  907137  309470  578634  343958
738411  48271   734278  830171  179620  825361  588190  447256  248883  250642  51866   32620   302956  806630  935173  928321  204378  202732  989099
377440  324634  778147  608384  785065  50113   956011  489787  487493  759017  311856  260729  372281  343418  430775  577443  430364  968287  557071
265886  580527  152550  469070  326433  281973  619842  246198  593157  88762   3774    758046  814625  800907  709085  681431  819129  635700  844335
44119   671132  348749  276241  749294  4992    829247  508949  970807  565062  335222  248352  670201  742223  349451  8315    360250  308669  14237
377857  211144  681144  636528  981268  376699  808462  171592  622777  252247  189519  735690  15554   371921  451361  490911  904659  324159  464376
209587  800272  890806  449407  942824  290015  565740  739152  409083  430094  660616  479428  444625  848605  800171  490971  627733  443137  435421
801200  959933  631898  269602  405283  534671  765138  204309  453429  900143  782400  740891  186257  580689  457187  371113  784866  498480  188682
975442  849302  25310   273423  392339  344208  458617  490400  448864  996087  517646  832110  726874  703651  724241  313039  141414  652153  543798
462344  268771  297851  353763  424815  584959  249467  406309  405099  176104  367209  950205  139388  223292  822733  345252  10543   608156  631854
859965  567383  262383  19263   292267  669954  222631  865718  744915  326296  344562  783673  539245  436250  690225  795125  898847  291740  875210
930073  809653  258753  168526  294396  757218  316524  612310  274477  893636  129957  934066  512775  539139  189019  146186  477834  302953  620655
133762  250270  788392  833588  760946  101207  610591  726121  834131  926696  321708  466277  379133  953584  528395  790503  648973  347518  603546
277757  510165  47850   979389  193717  238359  262263  139203  14287   70566   473391  228220  975844  783466  277047  568291  331198  652284  201120
388306  205307  563407  329662  239544  848887  982113  117889  800065  63670   72895   965516  302481  439157  595678  656517  347904  248339  787059
700220  787740  812873  37917   591792  675882  97672   872608  421604  628763  925780  549758  71860   387410  283854  106545  421981  419242  245629
711652  16134   736305  628664  462164  494254  237210  61950   529705  506663  76148   95955   527442  374955  619310  921600  565868  716051  462091
985231  654730  553537  316747  324652  761392  679426  699474  414028  223290  435272  545735  292201  514711  663502  139547  514484  953159  810180
894485  954488  982523  99422   692732  487402  466121  594620  918078  148909  820424  254309  376446  805200  82074   955855  148013  740709  191847
217212  763700  420440  717897  802758  382660  297241  680913  111024  613197  180679  199259  774289  575545  437215  76848   226697  918854  159007
652612  962730  529373  843509  158402  345 318321  709299  505585  676879  941617  739323  853186  417987  735756  85478   432425  720372  233965
928428  919054  401691  520593  182891  105051  249395  129407  395425  154579  5546    144942  652953  729793  212303  963649  170534  254115  184373
540800  955373  33395   159030  426384  695909  377395  722850  774838  311340  615578  120019  240787  663428  443013  815084  117956  546466  186623
548160  555914  756431  524384  430584  675772  248 728842  323131  1275    959957  383312  402348  326893  471212  868213  576896  864786  237896
361442  556809  879936  125333  422895  49778   442627  612070  333626  380651  646938  477648  140864  953269  524115  815491  168527  618672  859019
132834  744569  538240  655452  414010  332317  831477  639356  51603   871713  5208    782347  352046  557404  12092   899001  898282  742830  214911
505057  461227  397586  717315  18759   219244  304442  636873  106088  769906  525908  720592  711678  827687  225601  269343  47223   169432  256030
732481  534486  256600  394657  435897  19855   67689   373244  399137  921751  580110  544637  921728  482935  824887  707240  653975  663790  764878
572824  401021  597696  959124  735963  689542  710305  632516  743957  418419  46933   502974  568653  772405  410425  263787  899568  186105  879592
46616   473752  610221  621179  659082  999457  87009   814176  3129    121649  242166  55525   413194  170760  73078   530753  210886  491578  622444
974046  750513  504529  310016  638220  72901   794357  314725  776902  715319  148480  813863  778211  3607    599711  76249   784346  195250  886200
636781  130812  753566  832410  933715  733160  586305  933737  334356  742482  21285   632534  138347  69946   936887  477200  797634  975547  207174
189180  786863  529494  949490  591354  808868  819743  370172  272304  712543  34060   851026  899957  572564  806373  751054  437675  938059  10343
305560  479746  494423  308914  234564  973241  697418  84248   875828  758942  339092  403553  182895  869334  871547  281802  341183  423756  438922
658911  220082  423792  103672  668024  112839  500680  70993   738323  947716  369506  389346  104064  23869   457034  587992  739486  368555  387691
298154  846149  602980  356295  682649  409390  185295  289400  858561  920515  475677  388118  325903  829027  144139  337369  112740  52556   449795
854973  744288  779089  447163  270094  558702  852654  24756   918089  963071  871031  617649  691172  960656  977880  338465  166115  441011  13661
793609  418894  357367  569858  654499  525229  866015  910350  172077  142441  703570  322538  77682   201059  527763  3965    587014  93933   379377
486410  380321  458750  640127  510683  532233  894934  970991  152376  743774  51955   786768  453021  935148  574774  106873  254517  114433  556221
903247  529589  380389  847973  579807  603759  943405  711176  251037  861294  237672  544132  482182  186411  339034  20488   478979  898712  394496
701768  56036   839428  72187   699857  629241  995391  775156  576022  457734  853848  352669  314344  732031  682844  381033  725514  87254   915405
79003   4044    466394  516847  296010  155027  615033  872225  523141  523977  195480  530873  502151  317306  839347  661795  58895   145101  10354
381795  316174  993065  643264  434205  43360   75263   921716  275679  784847  800414  203998  94906   28002   583691  252530  457271  890659  236033
28819   712319  284242  216089  373461  698113  361825  10271   322269  42944   703749  461261  611712  496206  447268  406644  300814  909648  353792
493469  662533  515325  51381   684592  572433  172010  510493  591274  374016  116996  51778   146956  780841  280319  71458   370418  283400  236962
200609  623542  690293  903087  176189  545805  289215  925502  300012  366547  885792  205200  788515  391806  553872  826265  510315  685833  102261
749326  892978  969112  961059  526383  744985  572758  482880  132226  524172  124638  865895  828621  398468  286405  630279  564765  850117  50185
26081   350298  386139  118241  345298  271004  561323  824411  418750  870610  590394  929985  238032  292634  534450  367813  744563  965095  550853
286804  570241  283333  199653  144629  360644  937613  879060  562589  11975   445751  883820  184707  892961  688035  970188  634831  99156   607875
605954  431241  888725  277572  949136  150898  725169  401576  798563  108644  799602  65013   99769   994719  42517   949042  448038  316379  589901
977685  56486   523254  272090  845543  536032  654179  549148  111854  871081  456879  231975  444298  171580  260610  419349  108746  665692  415049
581286  736382  79868   495052  967962  503485  508683  202321  101849  735193  518376  849113  227467  982366  885845  437313  899642  297148  887984
736835  553291  202585  304302  769207  295135  622685  932539  78545   816751  477350  371947  183467  466049  231802  607056  569631  581565  865039
568916  558151  241469  957318  168219  938892  448782  519543  834885  643491  33096   805448  337756  40841   592491  96904   6426    756154  550259
509978  757837  228617  60716   73286   866426  665747  732584  623140  375873  464018  221448  977960  719463  130463  870769  64951   615366  570500
665086  299466  152093  67353   343137  605212  571823  554080  869692  965927  756017  528018  204889  724118  40919   512464  564010  191118  944715
964078  303493  673775  147288  430143  55075   617556  830018  23918   885716  299270  680034  492501  971317  685100  156167  873702  901195  360396
787883  870703  585550  887711  681325  75471   183260  500464  740809  698800  832136  911620  881770  78110   454336  816782  690486  639617  964298
442008  335440  182245  256318  497264  239254  897779  35202   765568  527256  972705  206468  124079  131917  295612  366347  404910  909935  895872
707892  686407  95071   428524  903125  825933  863009  894263  980975  976121  283928  37457   865796  229110  527508  596445  562062  416806  155436
745200  438639  190734  292451  203563  153193  965056  318101  758591  492942  651802  935921  900035  342604  222435  436303  29005   903976  622348
785839  484399  855670  971107  683266  291946  926081  426655  736835  787246  310443  435555  314621  764247  369474  541322  521368  650995  253698
776455  469272  668961  838807  406265  619670  216162  946758  134685  926785  560635  747096  576681  78041   962667  450487  554421  364291  544767
141133  211807  656670  724810  123278  160003  346165  99137   733169  156445  251042  1044    477298  47469   745811  936871  693772  83793   533599
147589  667141  990065  293959  652065  400645  66612   494038  989615  289095  788106  311586  146039  600798  465474  31195   966597  269442  668267
125191  635710  432665  780454  936219  838125  159508  640431  608132  79189   83019   41534   759631  907946  122815  898910  455816  664078  559791
597845  505265  345815  399603  395126  491478  530707  678890  748842  338437  788861  249371  243584  218172  911879  12566   42399   796368  908716
254406  258252  65197   556329  735550  396879  448857  72318   834859  304655  936241  740373  491386  439268  44817   961427  534382  656442  851913
247282  6445    562233  34309   971116  316021  373580  251996  534036  666787  709185  469499  545264  242167  889314  955413  464460  692802  212314
634657  204454  539578  809018  60924   994138  147689  232372  250654  853609  719301  346139  90254   808568  292093  681436  795085  409476  499633
661519  46913   709321  883124  525858  165082  235928  817067  626764  469843  734286  927234  143671  392015  607337  913345  882183  800297  778919
110664  348209  276054  919019  945168  844396  340476  253456  750904  192103  849965  345017  457153  208942  502772  893283  922180  355691  792107
70286   876169  65794   447412  139224  981740  770111  658779  827639  735399  733379  628064  780522  763457  335656  643589  683319  868825  909742
258697  295944  744572  206889  508579  416230  878438  400804  830094  383960  721664  620986  437288  448897  998730  586021  458829  738807  70938
670183  375426  332485  992204  613698  457108  901012  569508  459979  994897  345589  909615  883509  475568  364747  452035  852054  826389  396530
818600  383303  556122  855915  726286  748638  405412  593755  230082  6457    183818  20053   932593  925246  713649  306591  510242  509258  603471
805735  443698  870378  548382  376867  17972   340219  899998  106978  440162  555149  834010  895801  672813  275594  4348    326480  340281  629873
765736  226981  774979  555180  96606   42928   829396  391487  683068  951396  706189  424350  993595  370190  404944  796707  881550  883980  461224
58021   608264  746418  677398  648887  527682  952638  125522  421704  884776  813701  170462  193890  693229  735933  67961   27843   477196  521466
393289  247065  567461  202455  396612  22201   45062   616931  306901  693466  199112  365071  194834  303633  891290  824889  355315  827470  696733
117197  206819  64800   247518  386012  622494  613863  560775  316668  549228  599772  948006  948343  42850   249725  501451  150523  168751  314084
180592  655086  455512  204939  746978  849494  397862  214573  485112  743647  816914  266032  939593  168326  773361  310419  774555  164293  554939
657433  888888  39315   80601   981305  28096   850576  304385  563384  940409  32346   105317  911602  88429   616910  365269  594147  704459  123462
107262  159943  975756  710212  404943  508826  935724  845386  462400  835484  505877  429618  345188  518717  550619  193971  892248  988523  187719
60873   81202   461284  940394  873515  150463  688191  997795  514722  166218  971901  838394  333424  847432  473485  27729   471001  65633   344513
85516   384013  811890  743228  172564  588404  147011  829781  815748  948995  479064  586592  302740  308698  72478   458421  489559  870788  155092
575231  933389  901617  510801  999091  345147  177610  326621  954319  181380  51335   92573   275272  81761   945970  750469  744952  537589  161434
461732  568422  474919  449031  878201  338186  377553  931436  850178  412777  857443  589208  178416  3289    752273  204440  336402  286523  65433
424427  911581  62173   168307  882454  586094  500731  206981  14309   406018  939172  95450   610226  641427  90263   665389  29433   855491  995187
825367  843348  517219  345947  729467  845274  824408  828027  439690  759021  40074   573859  183776  523734  636302  207930  959376  682751  936895
780870  397808  888793  489102  198169  628271  341953  485237  388678  921108  365399  114571  857411  498121  71407   371278  912889  228085  621163
136151  804340  881901  98266   225347  868655  683154  393583  933952  431256  607257  997728  593567  113576  608666  302670  818985  481256  149362
124037  790940  562700  436548  772538  482071  465688  642736  465876  739875  680486  271781  707162  294118  351440  169348  392888  630655  820318
326790  703722  894363  599093  673050  496538  501619  263171  812791  831805  807862  260530  379912  810442  104651  941696  515630  204147  786820
312054  749659  500991  333376  686194  771965  374005  397206  614377  857318  604041  574171  946332  552692  276387  761933  752516  451200  274526
255299  348098  789117  161950  511374  151223  273155  995514  932285  533828  494429  139599  321810  984846  995709  324797  303085  823845  846328
485973  903444  202949  401908  276332  277452  274593  629840  754061  670094  153644  753273  784348  945431  255883  967672  896893  161929  719595
606010  560818  983041  279830  538615  54711   685389  781572  141856  868555  391675  371601  597642  609119  25276   374443  688472  219493  331414
308277  196150  967154  871569  474587  473758  580366  221721  627489  328270  969555  948505  908952  281271  318817  726574  931521  495533  911382
641009  511757  213335  837406  974447  256047  14395   886320  407926  245479  476650  613563  479007  702659  777327  218251  478066  345583  844923
967413  253280  486465  4444    227356  914114  888890  319731  390571  165441  100819  737969  173510  237882  534115  706598  655609  37112   789788
996538  412902  144087  704827  617776  641652  561127  903009  598764  432959  232389  112927  960612  911599  276605  748349  182355  173422  173293
743588  130904  961020  501075  278692  895716  835047  193643  965754  175769  799782  74006   359611  871009  269309  592930  643580  173756  273484
590637  663765  538696  786559  868383  728089  867872  110034  359416  46910   75915   779881  471357  927768  108848  307323  881935  639778  20619
47809   648572  925141  773775  402651  713850  264222  8460    79187   663706  332124  34078   789564  768370  361320  944592  502113  713658  401545
576750  784409  757902  532621  866900  118685  573767  888857  479380  863636  194265  474873  710825  101026  163613  58203   442107  345117  516966
538856  485221  28821   602496  250918  966126  294166  981436  905223  215511  474454  51116   859497  567385  614398  59716   206821  416338  854558
360139  474275  112865  880039  979071  173896  56881   118170  434943  562892  600377  856361  877022  42438   386803  452436  153032  846245  695347
938064  889966  930150  202932  230431  137318  296950  139198  542135  152152  949025  444559  6673    922588  478179  371594  225563  113802  692382
271072  846829  666189  612186  236830  322138  572317  660873  111918  931795  905178  840794  166703  890589  737780  403145  195990  906554  460970
800515  728831  429182  548611  411908  687595  314929  724456  87593   89271   525111  72695   56273   900549  4619    831573  164421  617767  95990
91293   962719  968492  135614  216988  881842  582574  993364  217718  456993  69803   577865  176884  815998  468980  286537  933086  222552  537633
592881  27204   535429  734482  921660  444398  94352   823452  492918  845998  334876  222079  932269  88160   390425  105386  692076  554528  162503
311769  263534  303889  961852  855579  525766  981805  905652  11877   104419  128821  696472  151453  460143  328234  771108  75742   313797  901506
321705  105621  865695  294426  33747   679238  440031  947437  462093  325662  950254  200431  538234  165894  126401  874118  868453  230512  551667
340915  20726   910982  308927  237762  622337  510637  470515  675921  294484  796040  394231  967041  200776  152885  936684  468193  22049   577732
985728  897672  324630  915006  742442  796368  15203   898281  306794  458625  211906  268386  930987  952707  549333  900418  131276  607013  880165
502542  496310  783108  174754  868835  807230  401279  861770  239896  572216  39995   196771  782064  88447   721075  846467  205861  277152  702618
937178  304914  794858  325952  459471  561291  655450  389468  314597  747358  163239  889556  352456  477229  843076  816615  2255    138810  151957
508257  773698  505282  730447  43224   664449  296932  994427  899633  191954  630002  888545  930846  939929  415324  763724  499398  915896  838208
259916  937585  769987  567497  771998  980098  264626  383679  635034  56721   54178   819349  932215  446018  853960  696018  732195  455566  890045
25902   578414  494158  566461  511813  65501   235870  640993  589298  288635  650943  116526  523889  56499   487579  38123   987826  418645  68778
268643  428295  239305  9062    366197  723204  878032  620048  669061  154784  135266  885397  39791   151471  124341  351596  407290  153164  658612
146720  676327  661013  823045  852116  445009  747811  272816  559101  225795  261810  397561  338694  431000  797566  3381    471901  649018  915829
392739  237271  679425  642962  910705  284025  399039  54350   451219  145322  395655  387415  537390  342709  26118   569955  4636    427659  13403
350275  800724  452214  314308  64274   516782  26667   63373   501361  973188  827474  741578  375603  515753  561138  121910  289338  889295  227615
378027  557407  311362  801583  311790  221586  76456   636389  596922  90377   288871  94261   867737  191642  341197  691785  104375  785190  716690
360041  559289  357399  432565  132127  354806  277581  739598  989294  549562  980068  362462  613352  26630   664821  896537  749748  298375  605799
851663  162614  78623   973261  361094  556991  95407   43473   804665  205231  777961  945687  706064  792213  516449  368940  440362  610731  679257
3522    365661  982072  980976  40261   404079  241914  852626  377667  838455  813470  586984  625554  510609  43911   804250  993738  439076  227437
769065  925707  918767  201581  110903  613208  90553   290479  691187  295289  403640  132005  291090  64694   789149  593044  181899  195902  220791
849822  660653  825118  786683  340165  52718   128906  75277   468627  559117  545924  645847  917578  329169  642373  328911  753279  596724  683996
266131  16962   912606  743767  253974  544602  400096  384421  812591  353454  702637  914492  765021  221574  538357  175978  853892  666069  827129
570041  571713  672279  619164  442414  161853  31514   3624    338871  613593  828388  878395  54184   617369  358110  324649  740790  606588  622429
479630  960111  954497  327743  586094  107006  457941  616205  215151  679805  663132  886037  399762  23511   540794  61445   515144  991829  867251
955026  555188  545287  17813   877840  677387  765257  560629  381747  289587  971065  803763  747217  528836  794958  37097   661263  52840   395838
831738  935643  786394  570464  337923  562190  541068  225053  915686  965111  608994  897447  846860  108752  515542  836528  764000  789307  568648
723470  342739  494286  351160  190884  749632  285933  593204  853796  468531  833461  600822  177790  71903   57017   649707  814314  902198  265691
49568   736471  665268  727451  228241  735293  266214  953790  746801  445968  242866  116621  77898   24034   500331  757553  417475  584000  15633
557524  411056  61025   672145  502926  878605  900910  296864  461080  855045  218014  410273  336278  598272  800982  280759  228947  697911  891837
543467  58593   101761  606039  520769  579224  954895  303666  711070  826766  835187  922834  975887  975559  871418  911500  706658  871996  3679
70738   211416  885639  222326  932127  813172  263857  968374  331272  200031  581680  776507  929476  368018  168734  891126  829681  639437  162978
664114  204046  750930  141865  363724  776510  1027    49758   523553  304314  138587  940250  152049  401544  498491  429217  517955  227908  879362
313974  291320  485053  226156  652119  795722  249826  508193  842652  255385  750959  602417  830531  873597  156502  81403   172733  903063  300608
846077  226886  347950  354733  183161  929453  812804  548124  494858  371192  73718   717848  264585  753817  114424  870529  230068  837886  823817
659709  680097  68715   284764  52701   374669  249328  434817  929041  151048  158301  31343   406449  323024  963833  34601   150302  121669  383300
509094  369943  985701  534759  906697  707915  724234  259242  265120  889484  313892  352130  261258  912691  235167  746427  681393  78896   587756
507454  439476  282083  576648  310472  415131  945451  763859  304373  720114  364173  114039  291742  426789  432469  708446  800243  481237  629812
674372  176143  701382  664308  832567  303388  521183  623124  676197  521210  804816  657374  620040  324028  577319  737399  780091  865829  979263
724947  800513  146340  898853  743746  807026  490360  499247  539612  975203  102625  149163  582467  211472  235525  142002  967499  977292  194333
698755  657883  925237  563202  811528  499877  742543  924670  770401  382790  781910  761098  992670  822969  38111   547316  737032  514447  408979
342354  509985  15314   833975  980111  872985  53937   92361   135115  493793  26558   387989  749863  473400  14095   828533  346298  90713   549179
661293  317396  51811   570030  101184  709542  159113  933039  149081  95224   871687  675859  359861  868995  787585  839004  749815  312954  48850
254263  961809  615568  901794  133356  129135  414477  241648  139970  96901   40210   263797  652343  54635   261101  695132  344587  434734  71017
301829  560602  239117  995351  186593  706237  200285  149018  735391  615552  880644  333918  460496  79724   365075  980445  174677  342740  722726
567878  540321  725976  241799  49503   950624  709030  912228  45047   90467   662192  544900  706089  432177  830390  34270   641107  979295  180618
629513  868768  401203  786980  578171  895713  777520  448430  709841  277706  670686  65550   334298  565868  156586  539171  279713  582402  183752
818337  988697  826563  500005  514798  95384   545824  845969  571573  889383  228512  589517  532813  402211  278964  617428  822815  596597  594477
761243  535808  980674  883246  894445  167720  356057  722560  800290  277268  313019  263922  222411  998412  729962  329347  276817  289688  736167
440817  276618  296506  186137  361212  232830  607821  839875  126746  437730  968128  853883  155718  872036  346424  235862  871295  782533  499429
445919  187398  318460  4150    189620  6055    655334  502172  203042  355004  460583  72362   989439  146791  298702  933494  692845  254550  676772

FV:

0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18
179649  162287  315188  558753  228501  59621   714371  568347  850209  846719  167475  678523  51383   748690  76662   363069  249067  846662  390053
700267  852444  348174  597239  392771  6498    204889  688379  981302  394213  696835  556868  110040  441295  410151  768194  133584  816698  988167
614890  359655  320294  262335  114645  89746   508261  809266  690199  579084  879805  675755  607496  649244  7094    496436  417898  96573   641146
940426  824833  274368  249109  711229  587460  228851  455731  15842   715164  294340  884487  991480  771614  813940  310033  621535  322484  852765
790782  558112  520653  214459  287395  191823  707752  581333  489620  370686  46868   854189  204974  978979  789813  562844  739547  870338  670224
222022  658412  433784  991965  501848  881799  515420  102238  323596  565934  523158  990674  174526  802863  857750  372837  767927  665477  264223
941741  888673  305426  19606   344463  800571  922613  363948  989784  432094  747751  406421  367945  342563  287772  891768  373083  356337  575424
938327  664634  370378  694913  331224  161118  339929  252456  866538  984515  126731  403340  672485  550371  614551  204529  126258  690739  292861
640763  343284  549927  171331  12536   426832  388101  420322  122186  99169   166189  930257  468341  985209  718282  236464  150594  126579  657965
639419  462148  580505  159478  447775  481138  991770  951848  771566  745507  217388  197321  22588   545644  545950  162052  96006   226547  939065
52838   472172  787067  203371  969421  954374  186349  233521  877702  610792  775936  558621  685556  524084  60237   198500  708065  210410  609380
806701  217046  416264  452289  964307  743663  213364  544662  170249  657108  236755  786374  653926  929556  897227  712428  684426  404614  506199
810797  536133  293157  218807  754414  980741  178935  571046  149015  262543  520573  44001   543130  537197  707343  286510  899643  58355   144498
668244  500649  639778  789143  985868  889524  974427  351094  827237  793918  699917  286692  703557  77093   633090  686280  834005  209624  227889
894334  959536  929533  844074  139808  112510  353197  145556  408846  484932  793378  434664  878345  314541  142567  152479  524888  699946  776543
619468  705689  679435  468992  203186  699382  375687  185888  604635  747931  996590  376368  256627  913645  144239  206504  160178  819894  366485
19298   722675  411716  571684  79299   428462  882604  790594  196528  880779  157594  635893  155958  140592  372285  619659  294967  3296    998494
869440  793672  286300  116715  136643  199791  784384  281581  84242   227735  632024  629809  687930  499512  951571  538792  943883  515430  610488
994319  747497  869817  223000  683002  227138  342965  744285  883645  699714  631317  953153  758192  753375  319559  743533  576722  461995  796564
488863  70533   603197  669549  110931  856772  489350  702272  421909  184937  495246  186148  563470  365216  132100  255928  243613  524330  872870
718622  23211   62772   559587  277569  822369  70117   446651  383790  830122  638514  853866  995311  929531  523596  364609  46104   509052  294001
124866  724445  85441   805212  937835  220149  414969  894593  46959   214770  766724  515955  322454  715940  280395  342034  967671  869775  485684
118881  382419  460160  562819  190382  73175   271185  522180  848270  550684  355010  757558  673275  211685  73335   448302  323433  529942  552768
943575  279626  138873  375516  759809  713671  170098  448961  705994  990340  251376  424516  203864  388440  134114  465064  393845  111796  235562
756286  6858    630227  451748  195184  664304  851279  273110  723975  769643  951449  28985   137751  778617  378640  425406  712668  577396  252964
287833  778058  869763  867833  835946  604761  12019   190752  517321  169816  464703  780532  79885   743269  511106  220679  376626  644153  790063
825569  174231  124952  109564  225039  42698   691058  867735  36845   11738   995208  27333   63106   960545  727010  537046  399215  992443  384638
288610  759079  895006  984208  23048   815153  39275   544326  391068  1147    452709  145437  390284  430995  136148  821090  982345  532008  817538
660932  541978  767954  378680  80023   63108   869104  720178  426534  48482   194508  580453  730824  962771  523947  780672  460091  217279  869580
529745  688153  684062  739126  306484  686420  687727  671386  432804  264419  392866  814062  767772  1240    675014  983002  423432  58443   717703
278659  481321  321150  364884  699568  415333  254391  302803  842237  145841  150712  887676  703217  315794  113719  133387  74604   257217  151677
104850  516963  757495  637255  211922  285393  934227  412228  762409  143712  616984  839721  761531  438092  559089  570397  439422  576090  471306
757988  217513  368521  563080  67010   22065   760512  596295  151687  930490  863847  619409  663898  140699  445266  810606  693940  570969  353998
314272  869964  68758   308408  246026  942989  13261   324352  379017  317696  758938  187274  531902  617547  814724  202940  600856  412290  170141
235689  154283  776786  262845  299568  510934  770956  720821  309171  695709  788639  465128  860560  43298   976277  169635  944473  200222  974135
941940  663944  141857  947302  660708  171719  493140  418302  561834  192025  905450  582086  95635   130027  357817  786049  580511  123732  584032
38812   614445  88229   676741  81178   913203  679839  886066  263752  498087  620990  801694  490129  320164  195285  862965  190115  457144  328553
21573   560310  155039  751364  452285  118941  442315  265157  726780  733745  228037  564286  491752  243274  292535  353909  476821  457339  568930
605997  823308  158570  438009  104439  715894  376827  517518  541179  96469   367369  817240  700655  851544  54584   588228  306656  391562  364977
678204  872238  883149  745274  203021  250972  154794  376732  545590  421759  965385  633941  998014  495198  464487  324298  819687  777700  979363
36027   931443  712949  730806  144873  273857  171219  822766  183251  695284  286240  130142  643771  747992  935775  801851  521450  332722  129849
314355  21043   673975  495454  547874  813846  977605  76602   324709  309457  483157  549077  640746  367419  664710  709267  350499  106166  921089
721983  822608  956176  13427   805072  372044  688616  775266  845557  144367  726422  935625  794481  75928   815876  427866  473279  616397  397543
596808  87804   960186  110935  96853   99333   186428  610861  537880  714972  369126  676420  586885  888315  968183  457019  619478  766372  311518
17437   448144  957326  352495  647947  93996   987906  495160  483193  209228  791963  850365  912736  881525  207435  438710  682071  998726  747676
782796  75255   824762  511990  314953  246940  452113  242450  691857  608273  9908    772511  163487  944816  734051  740463  376928  165638  876243
83690   486554  493015  888380  960661  16212   421021  72921   220756  756836  302320  499400  975399  171606  631994  348864  586177  266066  172639
397212  678427  33663   736541  180910  295086  483103  76291   241458  829976  515771  934074  696685  161700  407355  209191  103726  105261  573469
432613  209640  871311  970587  413200  567540  741284  454050  863100  866352  874331  783859  180185  664593  911276  140207  379589  289507  353963
876299  908625  28772   97694   346916  985137  278011  19556   605302  991773  615491  959899  992104  557664  434672  811508  412882  19249   448787
592685  468711  110023  426367  416264  967413  939698  337549  711529  512917  94397   645802  755857  540972  63419   752139  845356  621269  383317
649179  206040  545528  979464  253285  701745  126068  809737  198741  791086  48370   372591  164122  640796  551710  910684  818445  969789  526020
928498  15233   185375  640356  497603  471644  811918  766132  725101  618781  393674  478194  374685  572296  678504  222693  753324  846246  993696
20494   953571  642735  363090  776420  505740  120321  454450  87627   720432  367652  496743  598094  651077  645217  15196   803896  124079  700692
902039  181661  941689  862963  604221  302717  45900   108515  155559  144651  544380  280666  350626  630494  858304  680065  479111  170564  60255
811484  536620  607813  615039  357023  120555  49624   12923   276290  494325  988804  982971  324865  896396  39738   349299  635532  448665  389862
807805  947079  293712  541071  139095  890867  859812  85023   292537  893232  237544  807966  413393  868089  106849  993610  49756   401331  864693
414280  574275  838357  336346  35990   473775  129153  663240  18251   639429  988747  901344  519596  265661  70433   788674  813646  999576  621160
180106  731990  307876  524949  115867  172937  704220  283646  432432  350521  626598  853350  666970  504578  96422   203563  903132  335734  990022
668841  928247  354197  120932  832463  402145  237365  40029   71950   293682  936109  281927  518964  516470  233366  857818  143579  347447  593620
611377  778522  782688  293225  954524  59031   691647  243724  638399  215184  471668  738497  415603  161182  412472  590239  953834  232291  715818
297478  670918  414161  897300  341715  910151  143541  646156  6803    991572  954094  558806  160379  104534  580425  599058  249164  676764  859672
23689   260248  769663  975293  700540  563052  744649  67649   222579  644715  585055  615120  851577  572084  590480  125547  820776  345874  132849
590185  131270  757081  785190  148997  335718  818715  692586  406439  560663  537337  710783  161859  626509  960874  984612  344807  144057  375571
985230  195177  175616  656569  521608  255204  939727  366718  464827  200058  284383  258611  880421  878278  356128  248271  919475  334389  960880
489130  197222  838322  950076  889214  99417   866758  833159  214594  316215  894624  46549   780666  144533  17538   945933  397382  492169  536855
900763  468533  62063   755440  900196  935356  749645  583601  643797  91487   311507  789153  797861  9944    691743  506037  917465  955302  691801
605650  786875  757671  836297  24970   767419  208177  277378  448221  811377  322610  548886  21608   747480  343097  691327  767403  148183  582492
955415  920442  145384  179469  639776  648643  25465   996683  541347  428580  546130  827810  817740  50709   573353  212326  481260  700676  20865
792244  552340  450939  197259  783307  123222  674736  775129  813823  161634  243641  296874  572592  953372  631649  764742  333953  315444  66944
467153  802145  467400  981360  85530   494883  842682  51552   328636  552205  961689  268308  567341  875604  89969   896519  336009  666224  979096
883763  988543  793639  783247  797686  61426   877798  78760   120877  413801  542042  36506   685799  968741  287553  650844  707178  744450  341400
836711  997408  684774  693653  925794  653826  691009  105016  278159  397117  903177  696091  803811  240206  716548  709385  962688  680294  799723
712989  15263   62035   352909  573733  281705  248325  439423  672082  202220  959420  413100  693204  788545  191167  549434  679965  93206   202154
884038  354171  970081  258778  657940  760783  275437  759691  217264  885595  816335  237476  592361  409723  117037  711929  87525   901186  450024
996435  2856    79636   774287  708674  16367   39389   800055  862692  507883  50709   476734  97807   619103  272966  813463  635492  491805  802460
389489  773133  786066  103858  844310  219488  534931  128900  161182  11772   127380  651775  475562  715611  424505  177167  817005  510085  171438
119748  135078  26100   646431  628242  778815  153334  357927  54901   936695  454402  574919  849882  389473  597212  670783  813403  410902  951488
646960  26384   434046  638484  811916  904287  579457  125865  162380  904054  274546  431547  144036  951655  993406  503593  129037  264663  533240
642643  354740  838874  268052  613015  880202  801108  711996  347692  641145  345936  165755  108868  263644  701297  432953  471654  93420   131661
318720  320124  835804  964529  675943  569674  341730  951951  792574  624105  606626  254515  391083  551679  356827  101130  61735   266453  528258
410333  166935  232631  623545  970378  940608  891291  131574  185341  455501  788671  313081  192399  667742  775135  154117  724485  973589  436290
458720  425066  290592  226584  121880  613355  918434  964367  914967  561789  811383  391084  956103  473023  341104  389356  55318   285442  330989
687506  629622  556030  95385   71422   557129  652512  378199  263328  657111  829056  677939  823412  62188   223826  175658  918628  756537  715753
623435  527922  640422  43749   669177  636891  320437  688196  112790  468187  976457  626189  376066  301507  389293  191839  227331  343896  203403
857091  428106  922466  593174  43882   229839  538979  214693  579404  538744  532981  602782  768227  684061  224660  69997   771861  442910  915281
202805  712171  596546  84308   247665  389822  34249   565730  862118  898577  739121  264902  587981  129755  677316  414275  178863  995157  19222
934733  801079  940076  219751  330526  723365  203720  849493  82329   718318  591392  410965  56986   712445  687912  686862  396779  193649  459354
872432  334893  865470  444696  45755   809095  507425  348440  768708  808101  674365  38301   694119  426365  636760  970465  180527  641201  545622
316408  396620  182038  806921  862933  725253  670868  456910  216942  281742  979785  738681  554452  864155  142627  445857  263100  518269  504065
281053  984551  171706  367321  723602  8712    366800  800361  59081   593664  156837  63199   936131  500236  531773  383137  687002  101699  468400
614459  738692  443825  800059  631937  367643  243201  289837  431024  430651  653182  621837  139126  963267  834190  931352  601575  229028  670554
721501  562612  249332  51289   158771  556296  319658  346314  963900  242262  366598  426893  152387  380547  262012  211065  301428  856861  217645
881544  48887   211212  103205  443655  106974  644522  392077  351972  535358  406647  111833  154863  456421  648972  835149  315320  437913  186793
969961  149401  739989  112465  810027  763428  168825  99428   707896  250090  475075  509662  775522  832315  155898  969364  437105  491023  514508
744578  754466  919765  194133  858281  455154  515105  542602  28060   846565  984894  82525   257486  451823  455882  136152  861322  246980  764093
8571    450678  738755  593426  352031  508270  553072  675983  994405  75463   295177  287166  144105  433779  27264   757618  609235  233878  342333
510462  315708  542009  533239  96732   998793  21433   455791  702055  447057  581894  170762  359967  662497  551581  733001  548785  667144  537671
562914  342131  693194  657298  461606  77308   415959  203778  482248  285318  825498  888914  44020   749472  981147  942965  425695  970762  429391
36131   684735  409422  76387   928439  693147  497097  223057  265033  692048  901812  813357  271431  551296  225198  427956  15273   457059  926890
709429  668513  957995  64099   887726  336069  113689  973359  23372   447172  551621  735937  59028   864841  381963  488771  22968   853837  100365
211264  83523   856706  98101   919230  873797  823294  598718  727599  700256  11374   835599  880250  260856  459113  707967  531872  28608   682749
252664  830554  798042  69004   204999  564128  345225  109540  775771  987706  21808   572958  236271  350106  950498  427213  619 505508  500183
2121    520945  945296  972265  347166  606923  200285  824003  15700   57917   478069  222263  598542  765389  981171  44525   591992  742786  591853
79772   541559  982846  705732  512154  370882  549200  256838  756530  440277  635768  112559  663692  626139  316119  516432  886263  920354  27932
525668  344672  399932  549308  728164  961147  877394  443972  571066  168477  279587  596991  744761  893874  942334  162452  54771   972901  855782
710146  524454  885173  232656  502815  74640   447724  551992  281656  311828  971412  139166  736143  831758  952078  684793  244148  799725  818598
422248  770858  594912  255965  315995  516641  523123  126110  208086  620259  781012  170781  177182  249989  198331  145000  101554  863473  753170
31693   497583  576295  986883  634890  248463  48259   926642  618359  339349  838520  875555  380890  19912   11406   526125  78041   693202  411822
278956  884281  579037  369305  664420  538050  694470  196648  434921  514709  855911  276530  903234  612579  866627  376780  974459  932674  827799
630121  945194  913606  173561  540960  763859  145737  370247  252667  907951  528682  457935  52989   67692   661866  196178  876508  982045  585607
591937  574533  722357  523835  110281  613923  736397  781939  457532  532644  572001  537693  890269  98084   915623  583329  501295  326532  726123
906508  123555  67802   8617    35943   175328  480783  106073  139881  926335  120713  237490  976231  538291  196999  968564  125850  776219  296739
398881  148828  825596  178834  26623   549002  957007  322468  266165  948930  519582  138826  89018   131569  645071  657622  829352  817307  722939
59471   176241  982244  53775   75695   823830  866793  734806  335034  711954  717178  635142  844898  478606  25525   517471  339792  275398  87228
566061  956553  687192  458049  942966  891974  761072  658383  713422  244489  487864  699309  118138  130267  959581  506810  152713  74033   75377
916086  135765  135040  335955  641782  169386  82877   909742  723047  536638  301360  437189  221985  677680  7999    357915  613392  244492  377316
256879  531045  500029  425202  955454  686253  71496   535254  135273  521928  960777  925276  233447  348206  973918  270400  567736  453145  723384
711964  715771  45012   465558  586443  615286  873124  78530   268219  408004  251357  110924  183815  472039  954707  729460  440907  560982  882866
387128  947077  732747  130395  157470  51538   940573  439461  69088   704808  604268  357924  608724  975261  678255  885302  524081  30353   72176
981069  870105  270510  793392  195550  422956  252414  684965  729920  679673  508979  938158  436755  647480  534354  61009   587066  167872  814966
773351  416238  340681  92799   357279  678436  14272   286097  484818  704484  991087  549837  244284  634230  244984  944080  920107  17304   753863
236648  328527  152823  165380  692929  775226  519019  326866  194084  227142  820922  30768   641782  707123  87559   481957  695458  158298  25219
18488   879238  810633  264431  708777  765658  838426  764014  907886  938456  912020  917633  664955  240446  461979  468590  625688  657471  425798
414463  56149   912400  24113   496223  496130  969167  370786  754472  363264  219195  778114  54968   278291  803670  533195  357496  456418  291100
843809  80330   893200  973729  251474  90365   196135  41890   357875  867201  467167  393438  320756  687312  404658  400995  321839  159047  976203
141274  138001  756515  265903  550214  285791  999165  624967  221251  219818  722850  254227  806782  221535  347340  238035  721158  38019   746063
580386  344664  715604  398933  380242  449519  107057  369094  694822  910130  57423   850768  936003  340973  824359  718752  635993  191328  298869
800069  446319  423230  2463    799603  185675  420049  711497  295351  684310  881099  141794  623374  387802  27089   189473  907683  485305  82671
723949  179424  873487  205908  847276  209150  828607  811771  518242  404700  96982   259916  248451  980816  866199  78653   958868  676453  161299
728195  520745  191469  934973  93977   447981  108181  943758  379032  928083  227051  471212  335662  362695  94067   3103    824215  265204  845197
79319   341384  723536  207012  926902  888845  30261   273398  959901  437240  517804  622202  149136  594278  779995  524423  660723  412892  360458
471176  752996  938976  709512  38517   594618  315618  17874   437428  918547  854895  602905  162516  769786  414977  798612  434179  413433  839661
210544  566344  490178  853324  188917  13013   760382  763468  607917  884858  294558  811264  41018   693556  757643  215748  273957  919205  416283
771100  790512  696140  659204  458530  770301  81606   115706  93395   389928  591937  936923  449557  405986  902805  98086   54971   9333    731673
729344  238320  12998   103386  814187  775964  307336  183491  446706  55238   363834  285321  434107  484004  773927  282677  559979  302337  208792
644911  267660  616672  104511  418518  681170  818364  574991  179667  616991  637781  759907  795353  420453  380216  336821  884573  373795  548283
891026  420307  706212  466893  647519  104100  521320  281025  774697  724570  416405  642985  611511  871935  265907  262653  984293  753414  744680
123129  905680  163643  225760  206939  710169  388974  442763  232448  149108  456331  588044  928644  884044  148056  961753  684251  132935  560957
804146  24219   161347  378414  391564  634004  89044   231057  890705  837352  905969  793843  149560  41592   431381  54202   81818   144377  989678
294742  596092  630688  292047  9893    817048  853045  846393  607178  364833  932631  269158  305799  358514  4283    456616  133317  626196  186678
163845  931625  561505  634358  341935  854990  828611  809382  307170  938164  178151  747656  113811  675408  2441    689382  227219  780838  855777
461074  66673   404417  693888  261447  433972  281356  395280  796092  728082  916078  968370  339529  38783   159261  709709  656197  370272  418076
783549  868860  97581   887560  991785  887042  415903  435564  923660  832875  860479  133117  265016  670677  174949  216398  113984  655009  443911
768714  666120  283994  35463   843488  873857  86535   764843  170402  227701  319297  83634   988807  56350   495236  172097  571569  776416  491891
55948   959142  735641  389746  577472  991310  896133  587795  184541  506352  673714  99642   589419  786546  75973   85623   223262  408727  449720
619881  9993    786012  252030  697427  144557  618788  32291   916909  373303  943751  474902  304890  413347  949211  565851  962346  487354  950151
152079  617170  848442  151061  173430  933770  611450  37673   443890  515295  334355  817893  404250  352756  1922    302319  570400  53096   73468
59806   674878  136954  960470  627130  277312  311874  28934   776114  98243   392836  545988  809454  188068  49637   119227  120745  703203  174484
906005  531743  922271  626838  185696  266611  912862  724622  639923  64196   600619  434123  752419  944347  271789  668377  213954  828859  697137
921590  673632  849398  540191  428976  962248  755467  280913  346356  360862  383339  906734  149527  807318  182258  704367  440168  510662  993386
768686  195082  260784  305050  696639  627455  637041  771297  203110  773906  707082  556219  257047  410515  223746  625667  923364  327525  156297
843283  91170   830 897531  445451  919034  403497  634958  617021  350236  244278  297742  599961  104779  542323  658665  940082  918909  997897
561512  810707  57110   703950  934648  351513  840899  627513  523401  349648  878084  992203  531397  460831  55896   265807  278219  344052  594754
631671  408582  913987  975719  261407  251995  17251   592582  641258  775477  872362  145335  312265  214297  802023  479500  860457  677144  836119
571626  106897  346401  928726  885515  598176  74062   815615  540206  401318  67167   537170  49649   124006  363008  597700  656327  691480  354659
432644  976736  998955  103996  507786  233115  59988   121438  722268  272442  763959  842336  883028  73210   24305   30429   977637  591975  434889
133867  615418  503824  318839  595001  252381  500848  537934  396202  234903  619850  418257  791851  357008  96189   558527  477530  909933  552426
84364   482062  285512  515375  158587  910191  38739   267899  467308  236371  79696   852202  573215  453744  85796   402494  846120  948437  305415
251569  369329  644676  712043  398891  214215  176899  165196  452909  530716  322217  680254  616559  144371  66756   806994  946223  488078  759840
140213  328037  147033  274178  341600  204597  942048  765767  718998  722677  880969  937120  797273  315514  824134  175348  695427  420540  487295
793875  571259  797669  702124  884151  349617  298285  29362   804975  764767  285860  328678  191443  322891  650823  786375  279566  894735  377120
375580  76022   433784  325357  957547  456788  544310  468943  756202  358138  61843   229303  970541  342727  549942  188997  547001  141717  152801
623670  676635  217205  590382  549068  735312  464302  550714  886286  28164   591182  311684  143552  11909   731172  724828  154985  696630  982647
594569  26940   940850  853598  70858   754410  854311  535518  15018   842493  122702  526822  840974  39215   733720  772184  840451  858886  64377
466374  589498  46498   794262  54737   466474  289714  59484   225669  651906  151975  18584   92207   523252  849031  21687   683281  34863   425480
609658  981783  942864  766901  552641  787962  631906  340178  91921   579245  346229  384542  359368  941522  229744  626278  927671  846184  638355
845556  753307  698075  526829  337107  182266  136202  288979  865658  931821  581532  339540  9970    154410  46935   227696  70172   350724  582099
133543  186141  854629  743291  649830  548360  573154  587265  23401   493041  725976  435296  787021  768329  707247  418695  68291   744932  812604
163723  913742  996955  886410  855379  737508  564817  686508  189730  351319  185751  731203  626441  572066  62894   5646    874212  117676  988632
334753  929353  417921  497138  703469  585391  538783  422704  515943  695736  459924  580051  547158  275098  179773  872337  102784  996778  469929
39813   532450  651683  68040   96422   87649   719117  116415  33799   293118  270805  192015  205274  549662  555700  904610  254321  443114  802528
815818  581640  779534  175689  274098  110418  436321  631940  175437  686062  298856  708347  641341  146583  362967  470370  557833  486154  734260
434341  628820  559657  510713  708642  712477  503071  404944  620756  143047  332150  784295  498616  270965  192978  600975  531923  23847   348395
647827  771947  607261  149625  232693  663211  696965  887143  626059  27431   129812  19579   954107  335408  293302  966546  401194  17304   156900
578717  889339  932466  771024  754838  843864  63803   192951  178667  697020  526639  433412  370837  88137   841080  599263  459241  398496  753550
608389  197078  207160  470929  107608  237117  755235  274680  641421  20576   313860  488029  23889   241411  114774  121559  859399  766290  202132
412760  482517  169021  746368  373600  283944  989648  377192  206216  18614   434761  764743  604056  905513  681107  582395  5930    921643  296427
380482  181473  301709  564340  181385  303879  809260  344523  607850  525092  484581  59539   683967  858573  547654  179116  155117  796663  858651
917506  592467  856107  722946  965877  213179  608330  33994   914932  809536  590823  31248   731764  466490  408255  90341   820245  921091  868083
239381  904314  790992  771372  648307  937306  478231  56851   728292  994699  130731  240116  556997  672967  979512  424539  645145  949376  80033
376069  114933  252972  77950   568953  108474  947428  57796   520057  854701  115488  758723  217899  960396  772640  103455  328215  804652  827252
183740  152198  424707  941553  548825  862021  291441  648452  202376  638971  232853  760596  976750  159126  643668  199208  994109  412500  609935
971147  521431  503771  605497  601658  737264  577180  855460  363816  176342  196325  415268  88978   615893  229055  177122  119093  351213  910704
927305  808198  507047  689191  159784  418740  69097   164665  14995   414261  109834  66528   173404  662247  681151  140870  829244  141776  361699
138568  657414  195503  112556  269127  922361  299806  839713  955920  147911  955444  792788  792700  72646   509249  346538  89777   106293  60242
828243  125448  905138  99214   559594  326534  931738  29761   163635  872979  842318  292945  351458  806042  561820  310174  328686  33532   755070
662312  522091  702951  413900  749826  698408  983329  659593  413124  655598  541217  542191  437954  834092  272370  264650  270820  987912  261029
501092  94149   301766  203698  327410  499336  212905  42986   86814   69631   711501  274787  626228  182062  508797  155404  265691  424643  354032
900697  813825  238371  276355  813668  569357  839097  38529   407180  62774   682983  327632  913928  526214  572000  212712  71504   144511  688901
988099  897362  440716  406339  79833   988848  315686  649094  70084   632116  670162  50371   403414  186472  501182  439162  505514  904615  651389
380528  144845  456904  403689  825977  182966  750710  967890  926831  653870  23384   540031  912556  809648  612815  575150  441352  599126  687584
85692   699975  400221  989895  435991  953983  513634  174089  3511    791734  383809  755877  346530  270640  671946  751832  800846  803517  877557
405070  589395  468552  710036  876035  967562  901229  584923  389511  534969  111974  64448   734688  385201  733643  852245  379203  507633  579576
757636  16593   795955  905394  468772  751784  274503  25031   552807  161520  31903   305083  655991  745752  207592  89362   714401  699992  127732
813867  827298  901920  285373  317359  538704  502182  583122  218651  670273  501665  109352  288617  494518  599239  831826  224813  744120  843379
595979  244522  122655  667646  31947   683452  250218  957395  972215  911029  470760  912342  484047  816387  305270  269198  891556  870994  741092
274485  750539  321025  877228  831456  290905  921043  784991  873591  280770  941027  693125  593660  3133    673661  260909  70784   193917  397727
847947  719042  971557  751218  892761  626130  896036  734037  369823  865329  847214  826694  236415  161038  478408  537714  150705  936257  733978
765058  127629  1757    738187  823362  452998  754609  297656  58245   820390  585499  999684  998929  556242  351354  35521   921111  808698  421540
878502  78379   716633  34824   551959  438968  116037  92597   259566  481417  184495  256341  183106  38808   98645   623623  36512   844824  369419
279144  490387  621378  95485   975283  630546  628910  16573   474073  979323  214927  525500  168966  312302  29359   675826  915261  65340   933208
583273  694057  281171  516631  154373  547526  616932  484924  817173  270681  43949   28758   172595  305951  531169  952478  195688  323410  602517
868980  408960  377639  243813  933843  675622  569555  227518  716140  257218  608774  325202  910659  352173  390079  600378  745698  450792  471823
539702  119923  129046  377153  416083  182765  378306  588324  72921   452447  400371  132196  555425  786773  140174  282077  597433  730597  752011

LA:

    0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18
108502057   101127130   113821753   104723550   100424925   106417179   97368829    95380056    101339710   113636658   100785242   105127366   104402709   101579739   96902645    96765112    103895580   107746038   101792534

Thanks in advance, and let me know if I can be clearer about anything.

Answer 1

To briefly summarize your problem, for each of your column numbers (1-19) you have two vectors (FV and CV) of the same length. For each pair of elements, you can only pick one. You want to pick the elements such that the sum is as close as possible to the target value for that column stored in LA.

First, a bit of theory. If FV were filled with all 0's, then you can think of your problem as being equivalent to selecting the subset of elements in CV that sum as closely as possible to the value stored in LA. This is the famous Subset Sum Problem, which is NP-hard. Since the Subset Sum Problem is a special case of your problem, then we know your problem is also NP-hard. This means there is no known polynomial runtime algorithm that will always correctly solve your problem.

That being said, people routinely solve NP-hard problems in times that they find acceptable for their problem instances using integer programming software. You could define one binary decision variable x[i] for each row i of your dataset that takes value 1 if you use the FV value and value 0 if you take the CV value, as well as decision variable o for your objective value (the absolute value of the difference between your selected sum and the target value). Then you could define the following integer program:

min  o
s.t. o >= \sum_i { CV[i] + (FV[i]-CV[i])*x[i] } - LA[i]
     o >= -\sum_i { CV[i] - (FV[i]-CV[i])*x[i] } + LA[i]
     x[i] binary

You can solve this in R using a package like the lpSolveAPI package:

library(lpSolveAPI)
system.time(results <- lapply(seq_len(ncol(FV)), function(k) {
  mod <- make.lp(2, nrow(FV)+1)
  set.objfn(mod, c(1, rep(0, nrow(FV))))
  set.row(mod, 1, c(1, df_CV[,k]-df_FV[,k]))
  set.row(mod, 2, c(1, df_FV[,k]-df_CV[,k]))
  set.constr.type(mod, c(2, 2))  # >= constraints
  set.type(mod, 1, "real")
  set.type(mod, 2:(nrow(FV)+1), "binary")
  set.rhs(mod, c(1, -1) * (sum(df_CV[,k]) - df_LA[,k]))
  lp.control(mod, timeout=100)
  solve(mod)
  list(selections = 1+get.variables(mod), gap = get.objective(mod))
}))
#    user  system elapsed 
#  26.291   0.040  26.396 

So there's some good news -- for the problem instance you shared here, we can actually get the optimal selections very quickly (about 1 second per column). This is clearly much faster than a brute force approach, which would need to check 2^205 (more than a trillion trillion trillion trillion trillion) possibilities -- clearly not feasible. It is both faster than the approach you posted (since you were checking many randomly generated solutions), and also has the advantage of always guaranteeing that it gives you the best combination of CV and FV values possible.

The optimal solutions are very good; all give (up to numerical precision) sums equal to the target:

sapply(results, "[[", "gap")
# [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

I returned the results as a list of lists, which I think should be more manageable than what you were originally returning (a matrix with a pair of columns for each original column, and each column in the pair meaning some different thing). You can build a matrix of selections for each row and column with:

sapply(results, "[[", "selections")

If you increase the number of samples (the length of CV and LV), then you may find that the integer program may begin to take too long to solve to optimality. I included a timeout of 100 seconds per model in my code above; you can play with that to meet your needs.

Answer 2

I don't know R, so I can't comment much on your code.

If we strip away the context, then it sounds like we could phrase your question as such:

Given a list of pairs $$L = \bigl[ (a_1,b_1), (a_2,b_2), ... (a_n,b_n)\bigr]$$ and a number S, find a list $$C = \bigl[c_1, ... c_n\bigr]$$ $$c_i ∈ \{first, second\} $$ that minimizes $$ \left| S -\sum_{i ∈ [1...N]} C_i(L_i)\right|$$

(Is it guaranteed that there will be a C for which that difference is 0?)

Our total search space is then 2^n combinations . (for a version of the problem that represents one column of your data)

We can improve on your random method by searching that space systematically; just count up from 0 to n in binary and those digits are your candidate lists C.

That's still a O(2^n) process, the advantage is that you're never re-checking the same list by accident. I would bet that a O(log(n)) or O(n log(n)) algorithm exists; you could take this over to StackOverflow or the Math SE and probably get some suggestions.