class: center, middle, inverse, title-slide .title[ # Optymalizacja dyskretna <br>(w tym algorytmy heurystyczne) ] .subtitle[ ## Przeszukiwanie wyczerpujące ] .author[ ### Jakub Nowosad <br><a href="https://jakubnowosad.com/" class="uri">https://jakubnowosad.com/</a> ] --- # Przeszukiwanie wyczerpujące - Relatywnie proste - należy **w systematyczny sposób** przeszukać rozwiązania -- - Inne nazwy: exhaustive search, brute force -- - Zaleta - Daje optymalne rozwiązanie -- - Wada - Wymaga sprawdzenia każdego rozwiązania --- class: inverse, left, bottom # Przykłady --- # Problem komiwojażera <!-- http://www.cs.sfu.ca/CourseCentral/125/tjd/tsp_example.html --> Algorytm ```r wybierz pierwszą trasę; nazwij ją T najlepsza_trasa = T najlepsza_wartosc = wartosc(T) while istnieje kolejna permutacja T stwórz nową permutację T if wartosc(T) < najlepsza wartosc najlepsza_trasa = T najlepsza_wartosc = wartosc(T) wyświetl najlepsza_trasa i najlepsza_wartosc ``` --- # Problem komiwojażera Punkty <img src="05-exhaustive-search_files/figure-html/unnamed-chunk-2-1.png" style="display: block; margin: auto;" /> <!-- https://stackoverflow.com/questions/27363653/find-shortest-path-from-x-y-coordinates-with-start-%E2%89%A0-end --> --- # Problem komiwojażera Macierz odległości ``` ## 1 2 3 4 5 6 7 ## 1 0.0000000 0.2000000 0.3162278 0.4472136 0.5099020 0.7071068 0.3162278 ## 2 0.2000000 0.0000000 0.5099020 0.6324555 0.5099020 0.8602325 0.4242641 ## 3 0.3162278 0.5099020 0.0000000 0.3162278 0.5656854 0.6324555 0.4472136 ## 4 0.4472136 0.6324555 0.3162278 0.0000000 0.8602325 0.3162278 0.3162278 ## 5 0.5099020 0.5099020 0.5656854 0.8602325 0.0000000 1.1661904 0.8246211 ## 6 0.7071068 0.8602325 0.6324555 0.3162278 1.1661904 0.0000000 0.4472136 ## 7 0.3162278 0.4242641 0.4472136 0.3162278 0.8246211 0.4472136 0.0000000 ``` --- # Problem komiwojażera Liczba kombinacji ``` ## [1] 360 ``` --- # Problem komiwojażera Przykłady kombinacji ``` ## [,1] [,2] [,3] [,4] [,5] [,6] ## [1,] 2 3 4 5 6 7 ## [2,] 2 3 4 5 7 6 ## [3,] 2 3 4 6 5 7 ## [4,] 2 3 4 6 7 5 ## [5,] 2 3 4 7 5 6 ## [6,] 2 3 4 7 6 5 ## [7,] 2 3 5 4 6 7 ## [8,] 2 3 5 4 7 6 ## [9,] 2 3 5 6 4 7 ## [10,] 2 3 5 6 7 4 ## [11,] 2 3 5 7 4 6 ## [12,] 2 3 5 7 6 4 ## [13,] 2 3 6 4 5 7 ## [14,] 2 3 6 4 7 5 ## [15,] 2 3 6 5 4 7 ## [16,] 2 3 6 5 7 4 ## [17,] 2 3 6 7 4 5 ## [18,] 2 3 6 7 5 4 ## [19,] 2 3 7 4 5 6 ## [20,] 2 3 7 4 6 5 ## [21,] 2 3 7 5 4 6 ## [22,] 2 3 7 5 6 4 ## [23,] 2 3 7 6 4 5 ## [24,] 2 3 7 6 5 4 ## [25,] 2 4 3 5 6 7 ## [26,] 2 4 3 5 7 6 ## [27,] 2 4 3 6 5 7 ## [28,] 2 4 3 6 7 5 ## [29,] 2 4 3 7 5 6 ## [30,] 2 4 3 7 6 5 ## [31,] 2 4 5 3 6 7 ## [32,] 2 4 5 3 7 6 ## [33,] 2 4 5 6 3 7 ## [34,] 2 4 5 6 7 3 ## [35,] 2 4 5 7 3 6 ## [36,] 2 4 5 7 6 3 ## [37,] 2 4 6 3 5 7 ## [38,] 2 4 6 3 7 5 ## [39,] 2 4 6 5 3 7 ## [40,] 2 4 6 5 7 3 ## [41,] 2 4 6 7 3 5 ## [42,] 2 4 6 7 5 3 ## [43,] 2 4 7 3 5 6 ## [44,] 2 4 7 3 6 5 ## [45,] 2 4 7 5 3 6 ## [46,] 2 4 7 5 6 3 ## [47,] 2 4 7 6 3 5 ## [48,] 2 4 7 6 5 3 ## [49,] 2 5 3 4 6 7 ## [50,] 2 5 3 4 7 6 ## [51,] 2 5 3 6 4 7 ## [52,] 2 5 3 6 7 4 ## [53,] 2 5 3 7 4 6 ## [54,] 2 5 3 7 6 4 ## [55,] 2 5 4 3 6 7 ## [56,] 2 5 4 3 7 6 ## [57,] 2 5 4 6 3 7 ## [58,] 2 5 4 6 7 3 ## [59,] 2 5 4 7 3 6 ## [60,] 2 5 4 7 6 3 ## [61,] 2 5 6 3 4 7 ## [62,] 2 5 6 3 7 4 ## [63,] 2 5 6 4 3 7 ## [64,] 2 5 6 4 7 3 ## [65,] 2 5 6 7 3 4 ## [66,] 2 5 6 7 4 3 ## [67,] 2 5 7 3 4 6 ## [68,] 2 5 7 3 6 4 ## [69,] 2 5 7 4 3 6 ## [70,] 2 5 7 4 6 3 ## [71,] 2 5 7 6 3 4 ## [72,] 2 5 7 6 4 3 ## [73,] 2 6 3 4 5 7 ## [74,] 2 6 3 4 7 5 ## [75,] 2 6 3 5 4 7 ## [76,] 2 6 3 5 7 4 ## [77,] 2 6 3 7 4 5 ## [78,] 2 6 3 7 5 4 ## [79,] 2 6 4 3 5 7 ## [80,] 2 6 4 3 7 5 ## [81,] 2 6 4 5 3 7 ## [82,] 2 6 4 5 7 3 ## [83,] 2 6 4 7 3 5 ## [84,] 2 6 4 7 5 3 ## [85,] 2 6 5 3 4 7 ## [86,] 2 6 5 3 7 4 ## [87,] 2 6 5 4 3 7 ## [88,] 2 6 5 4 7 3 ## [89,] 2 6 5 7 3 4 ## [90,] 2 6 5 7 4 3 ## [91,] 2 6 7 3 4 5 ## [92,] 2 6 7 3 5 4 ## [93,] 2 6 7 4 3 5 ## [94,] 2 6 7 4 5 3 ## [95,] 2 6 7 5 3 4 ## [96,] 2 6 7 5 4 3 ## [97,] 2 7 3 4 5 6 ## [98,] 2 7 3 4 6 5 ## [99,] 2 7 3 5 4 6 ## [100,] 2 7 3 5 6 4 ## [101,] 2 7 3 6 4 5 ## [102,] 2 7 3 6 5 4 ## [103,] 2 7 4 3 5 6 ## [104,] 2 7 4 3 6 5 ## [105,] 2 7 4 5 3 6 ## [106,] 2 7 4 5 6 3 ## [107,] 2 7 4 6 3 5 ## [108,] 2 7 4 6 5 3 ## [109,] 2 7 5 3 4 6 ## [110,] 2 7 5 3 6 4 ## [111,] 2 7 5 4 3 6 ## [112,] 2 7 5 4 6 3 ## [113,] 2 7 5 6 3 4 ## [114,] 2 7 5 6 4 3 ## [115,] 2 7 6 3 4 5 ## [116,] 2 7 6 3 5 4 ## [117,] 2 7 6 4 3 5 ## [118,] 2 7 6 4 5 3 ## [119,] 2 7 6 5 3 4 ## [120,] 2 7 6 5 4 3 ## [121,] 3 2 4 5 6 7 ## [122,] 3 2 4 5 7 6 ## [123,] 3 2 4 6 5 7 ## [124,] 3 2 4 6 7 5 ## [125,] 3 2 4 7 5 6 ## [126,] 3 2 4 7 6 5 ## [127,] 3 2 5 4 6 7 ## [128,] 3 2 5 4 7 6 ## [129,] 3 2 5 6 4 7 ## [130,] 3 2 5 6 7 4 ## [131,] 3 2 5 7 4 6 ## [132,] 3 2 5 7 6 4 ## [133,] 3 2 6 4 5 7 ## [134,] 3 2 6 4 7 5 ## [135,] 3 2 6 5 4 7 ## [136,] 3 2 6 5 7 4 ## [137,] 3 2 6 7 4 5 ## [138,] 3 2 6 7 5 4 ## [139,] 3 2 7 4 5 6 ## [140,] 3 2 7 4 6 5 ## [141,] 3 2 7 5 4 6 ## [142,] 3 2 7 5 6 4 ## [143,] 3 2 7 6 4 5 ## [144,] 3 2 7 6 5 4 ## [145,] 3 4 2 5 6 7 ## [146,] 3 4 2 5 7 6 ## [147,] 3 4 2 6 5 7 ## [148,] 3 4 2 6 7 5 ## [149,] 3 4 2 7 5 6 ## [150,] 3 4 2 7 6 5 ## [151,] 3 4 5 2 6 7 ## [152,] 3 4 5 2 7 6 ## [153,] 3 4 5 6 2 7 ## [154,] 3 4 5 6 7 2 ## [155,] 3 4 5 7 2 6 ## [156,] 3 4 5 7 6 2 ## [157,] 3 4 6 2 5 7 ## [158,] 3 4 6 2 7 5 ## [159,] 3 4 6 5 2 7 ## [160,] 3 4 6 5 7 2 ## [161,] 3 4 6 7 2 5 ## [162,] 3 4 6 7 5 2 ## [163,] 3 4 7 2 5 6 ## [164,] 3 4 7 2 6 5 ## [165,] 3 4 7 5 2 6 ## [166,] 3 4 7 5 6 2 ## [167,] 3 4 7 6 2 5 ## [168,] 3 4 7 6 5 2 ## [169,] 3 5 2 4 6 7 ## [170,] 3 5 2 4 7 6 ## [171,] 3 5 2 6 4 7 ## [172,] 3 5 2 6 7 4 ## [173,] 3 5 2 7 4 6 ## [174,] 3 5 2 7 6 4 ## [175,] 3 5 4 2 6 7 ## [176,] 3 5 4 2 7 6 ## [177,] 3 5 4 6 2 7 ## [178,] 3 5 4 6 7 2 ## [179,] 3 5 4 7 2 6 ## [180,] 3 5 4 7 6 2 ## [181,] 3 5 6 2 4 7 ## [182,] 3 5 6 2 7 4 ## [183,] 3 5 6 4 2 7 ## [184,] 3 5 6 4 7 2 ## [185,] 3 5 6 7 2 4 ## [186,] 3 5 6 7 4 2 ## [187,] 3 5 7 2 4 6 ## [188,] 3 5 7 2 6 4 ## [189,] 3 5 7 4 2 6 ## [190,] 3 5 7 4 6 2 ## [191,] 3 5 7 6 2 4 ## [192,] 3 5 7 6 4 2 ## [193,] 3 6 2 4 5 7 ## [194,] 3 6 2 4 7 5 ## [195,] 3 6 2 5 4 7 ## [196,] 3 6 2 5 7 4 ## [197,] 3 6 2 7 4 5 ## [198,] 3 6 2 7 5 4 ## [199,] 3 6 4 2 5 7 ## [200,] 3 6 4 2 7 5 ## [201,] 3 6 4 5 2 7 ## [202,] 3 6 4 5 7 2 ## [203,] 3 6 4 7 2 5 ## [204,] 3 6 4 7 5 2 ## [205,] 3 6 5 2 4 7 ## [206,] 3 6 5 2 7 4 ## [207,] 3 6 5 4 2 7 ## [208,] 3 6 5 4 7 2 ## [209,] 3 6 5 7 2 4 ## [210,] 3 6 5 7 4 2 ## [211,] 3 6 7 2 4 5 ## [212,] 3 6 7 2 5 4 ## [213,] 3 6 7 4 2 5 ## [214,] 3 6 7 4 5 2 ## [215,] 3 6 7 5 2 4 ## [216,] 3 6 7 5 4 2 ## [217,] 3 7 2 4 5 6 ## [218,] 3 7 2 4 6 5 ## [219,] 3 7 2 5 4 6 ## [220,] 3 7 2 5 6 4 ## [221,] 3 7 2 6 4 5 ## [222,] 3 7 2 6 5 4 ## [223,] 3 7 4 2 5 6 ## [224,] 3 7 4 2 6 5 ## [225,] 3 7 4 5 2 6 ## [226,] 3 7 4 5 6 2 ## [227,] 3 7 4 6 2 5 ## [228,] 3 7 4 6 5 2 ## [229,] 3 7 5 2 4 6 ## [230,] 3 7 5 2 6 4 ## [231,] 3 7 5 4 2 6 ## [232,] 3 7 5 4 6 2 ## [233,] 3 7 5 6 2 4 ## [234,] 3 7 5 6 4 2 ## [235,] 3 7 6 2 4 5 ## [236,] 3 7 6 2 5 4 ## [237,] 3 7 6 4 2 5 ## [238,] 3 7 6 4 5 2 ## [239,] 3 7 6 5 2 4 ## [240,] 3 7 6 5 4 2 ## [241,] 4 2 3 5 6 7 ## [242,] 4 2 3 5 7 6 ## [243,] 4 2 3 6 5 7 ## [244,] 4 2 3 6 7 5 ## [245,] 4 2 3 7 5 6 ## [246,] 4 2 3 7 6 5 ## [247,] 4 2 5 3 6 7 ## [248,] 4 2 5 3 7 6 ## [249,] 4 2 5 6 3 7 ## [250,] 4 2 5 6 7 3 ## [251,] 4 2 5 7 3 6 ## [252,] 4 2 5 7 6 3 ## [253,] 4 2 6 3 5 7 ## [254,] 4 2 6 3 7 5 ## [255,] 4 2 6 5 3 7 ## [256,] 4 2 6 5 7 3 ## [257,] 4 2 6 7 3 5 ## [258,] 4 2 6 7 5 3 ## [259,] 4 2 7 3 5 6 ## [260,] 4 2 7 3 6 5 ## [261,] 4 2 7 5 3 6 ## [262,] 4 2 7 5 6 3 ## [263,] 4 2 7 6 3 5 ## [264,] 4 2 7 6 5 3 ## [265,] 4 3 2 5 6 7 ## [266,] 4 3 2 5 7 6 ## [267,] 4 3 2 6 5 7 ## [268,] 4 3 2 6 7 5 ## [269,] 4 3 2 7 5 6 ## [270,] 4 3 2 7 6 5 ## [271,] 4 3 5 2 6 7 ## [272,] 4 3 5 2 7 6 ## [273,] 4 3 5 6 2 7 ## [274,] 4 3 5 6 7 2 ## [275,] 4 3 5 7 2 6 ## [276,] 4 3 5 7 6 2 ## [277,] 4 3 6 2 5 7 ## [278,] 4 3 6 2 7 5 ## [279,] 4 3 6 5 2 7 ## [280,] 4 3 6 5 7 2 ## [281,] 4 3 6 7 2 5 ## [282,] 4 3 6 7 5 2 ## [283,] 4 3 7 2 5 6 ## [284,] 4 3 7 2 6 5 ## [285,] 4 3 7 5 2 6 ## [286,] 4 3 7 5 6 2 ## [287,] 4 3 7 6 2 5 ## [288,] 4 3 7 6 5 2 ## [289,] 4 5 2 3 6 7 ## [290,] 4 5 2 3 7 6 ## [291,] 4 5 2 6 3 7 ## [292,] 4 5 2 6 7 3 ## [293,] 4 5 2 7 3 6 ## [294,] 4 5 2 7 6 3 ## [295,] 4 5 3 2 6 7 ## [296,] 4 5 3 2 7 6 ## [297,] 4 5 3 6 2 7 ## [298,] 4 5 3 6 7 2 ## [299,] 4 5 3 7 2 6 ## [300,] 4 5 3 7 6 2 ## [301,] 4 5 6 2 3 7 ## [302,] 4 5 6 2 7 3 ## [303,] 4 5 6 3 2 7 ## [304,] 4 5 6 3 7 2 ## [305,] 4 5 6 7 2 3 ## [306,] 4 5 6 7 3 2 ## [307,] 4 5 7 2 3 6 ## [308,] 4 5 7 2 6 3 ## [309,] 4 5 7 3 2 6 ## [310,] 4 5 7 3 6 2 ## [311,] 4 5 7 6 2 3 ## [312,] 4 5 7 6 3 2 ## [313,] 4 6 2 3 5 7 ## [314,] 4 6 2 3 7 5 ## [315,] 4 6 2 5 3 7 ## [316,] 4 6 2 5 7 3 ## [317,] 4 6 2 7 3 5 ## [318,] 4 6 2 7 5 3 ## [319,] 4 6 3 2 5 7 ## [320,] 4 6 3 2 7 5 ## [321,] 4 6 3 5 2 7 ## [322,] 4 6 3 5 7 2 ## [323,] 4 6 3 7 2 5 ## [324,] 4 6 3 7 5 2 ## [325,] 4 6 5 2 3 7 ## [326,] 4 6 5 2 7 3 ## [327,] 4 6 5 3 2 7 ## [328,] 4 6 5 3 7 2 ## [329,] 4 6 5 7 2 3 ## [330,] 4 6 5 7 3 2 ## [331,] 4 6 7 2 3 5 ## [332,] 4 6 7 2 5 3 ## [333,] 4 6 7 3 2 5 ## [334,] 4 6 7 3 5 2 ## [335,] 4 6 7 5 2 3 ## [336,] 4 6 7 5 3 2 ## [337,] 4 7 2 3 5 6 ## [338,] 4 7 2 3 6 5 ## [339,] 4 7 2 5 3 6 ## [340,] 4 7 2 5 6 3 ## [341,] 4 7 2 6 3 5 ## [342,] 4 7 2 6 5 3 ## [343,] 4 7 3 2 5 6 ## [344,] 4 7 3 2 6 5 ## [345,] 4 7 3 5 2 6 ## [346,] 4 7 3 5 6 2 ## [347,] 4 7 3 6 2 5 ## [348,] 4 7 3 6 5 2 ## [349,] 4 7 5 2 3 6 ## [350,] 4 7 5 2 6 3 ## [351,] 4 7 5 3 2 6 ## [352,] 4 7 5 3 6 2 ## [353,] 4 7 5 6 2 3 ## [354,] 4 7 5 6 3 2 ## [355,] 4 7 6 2 3 5 ## [356,] 4 7 6 2 5 3 ## [357,] 4 7 6 3 2 5 ## [358,] 4 7 6 3 5 2 ## [359,] 4 7 6 5 2 3 ## [360,] 4 7 6 5 3 2 ``` --- # Problem komiwojażera <!-- http://www.cs.sfu.ca/CourseCentral/125/tjd/tsp_example.html --> Algorytm ```r wybierz pierwszą trasę; nazwij ją T najlepsza_trasa = T najlepsza_wartosc = wartosc(T) while istnieje kolejna permutacja T stwórz nową permutację T if wartosc(T) < najlepsza wartosc najlepsza_trasa = T najlepsza_wartosc = wartosc(T) wyświetl najlepsza_trasa i najlepsza_wartosc ``` <!-- https://www.rdocumentation.org/packages/TSP/versions/1.1-6/topics/solve_TSP --> --- # Problem plecakowy https://github.com/akilahmd/Knapsackpackage --- # Problem plecakowy I <div class="figure" style="text-align: center"> <img src="images/np_complete.png" alt="https://xkcd.com/287/" width="90%" /> <p class="caption">https://xkcd.com/287/</p> </div> --- # Problem plecakowy I The Knapsack Problem - https://www.cybaea.net/Journal/2009/07/10/The-Knapsack-Problem/ ```r appetizer_solution = function(target) { app = c(2.15, 2.75, 3.35, 3.55, 4.20, 5.80) r = 2L repeat{ c = gtools::combinations(length(app), r = r, v = app, repeats.allowed = TRUE) s = rowSums(c) if (all(s > target)) { print("No solution found") break } x = which(abs(s - target) < 1e-4) if (length(x) > 0L) { cat("Solution found: ", c[x, ], "\n") break } r = r + 1L } } ``` --- # Problem plecakowy I ```r appetizer_solution(15.05) ``` ``` ## Solution found: 2.15 3.55 3.55 5.8 ``` <div class="figure" style="text-align: center"> <img src="images/np_complete.png" alt="https://xkcd.com/287/" width="75%" /> <p class="caption">https://xkcd.com/287/</p> </div> --- # Problem plecakowy II <!-- https://github.com/akilahmd/Knapsackpackage/blob/master/R/brute_force_knapsack.R.R --> https://github.com/oscpe436/test_50-11/blob/master/R/functions.R#L48 --- # Problem plecakowy II ```r brute_force_knapsack = function(x, W) { no_of_objects = nrow(x) no_of_sets = 2 ^ nrow(x) weights = rep(NA, no_of_sets) values = rep(NA, no_of_sets) selected_objects = as.list(numeric(no_of_sets)) for (i in 1:no_of_sets) { selected_objects[[i]] = as.numeric(intToBits(i)[1:(no_of_objects)]) sample = x[selected_objects[[i]] == 1, ] weights[i] = sum(sample[, 1]) values[i] = sum(sample[, 2]) } index_OK = which(weights < W) weightsOK = weights[index_OK] valuesOK = values[index_OK] index_best = which.max(valuesOK) best_elements = (1:no_of_objects)[selected_objects[index_OK[index_best]][[1]] == 1] best_elements = best_elements[order(best_elements, decreasing = FALSE)] return(list(value = values[index_OK[index_best]], elements = best_elements)) } ``` --- # Problem placakowy II .pull-left[ Liczba elementów: - `\(I = 5\)` Ograniczenie (ang. *constraint*): - `\(W = 15\)` Wagi: - `\(w_1 = 12\)`, `\(w_2 = 2\)`, `\(w_3 = 1\)`, `\(w_4 = 1\)`, `\(w_5 = 4\)` Wartości: - `\(c_1 = 4\)`, `\(c_2 = 2\)`, `\(c_3 = 2\)`, `\(c_4 = 1\)`, `\(c_5 = 10\)` ] .pull-right[ <div class="figure" style="text-align: center"> <img src="images/knapsack.png" alt="https://commons.wikimedia.org/wiki/File:Knapsack.svg" width="35%" /> <p class="caption">https://commons.wikimedia.org/wiki/File:Knapsack.svg</p> </div> ```r pp = data.frame(w = c(12, 2, 1, 1, 4), v = c(4, 2, 2, 1, 10)) ``` <table> <thead> <tr> <th style="text-align:right;"> w </th> <th style="text-align:right;"> v </th> </tr> </thead> <tbody> <tr> <td style="text-align:right;"> 12 </td> <td style="text-align:right;"> 4 </td> </tr> <tr> <td style="text-align:right;"> 2 </td> <td style="text-align:right;"> 2 </td> </tr> <tr> <td style="text-align:right;"> 1 </td> <td style="text-align:right;"> 2 </td> </tr> <tr> <td style="text-align:right;"> 1 </td> <td style="text-align:right;"> 1 </td> </tr> <tr> <td style="text-align:right;"> 4 </td> <td style="text-align:right;"> 10 </td> </tr> </tbody> </table> ] --- # Problem placakowy II ```r pp ``` <table> <thead> <tr> <th style="text-align:right;"> w </th> <th style="text-align:right;"> v </th> </tr> </thead> <tbody> <tr> <td style="text-align:right;"> 12 </td> <td style="text-align:right;"> 4 </td> </tr> <tr> <td style="text-align:right;"> 2 </td> <td style="text-align:right;"> 2 </td> </tr> <tr> <td style="text-align:right;"> 1 </td> <td style="text-align:right;"> 2 </td> </tr> <tr> <td style="text-align:right;"> 1 </td> <td style="text-align:right;"> 1 </td> </tr> <tr> <td style="text-align:right;"> 4 </td> <td style="text-align:right;"> 10 </td> </tr> </tbody> </table> -- ```r brute_force_knapsack(pp, 15) ``` ``` ## $value ## [1] 15 ## ## $elements ## [1] 2 3 4 5 ``` --- # Problem placakowy II ```r knapsack_objects = data.frame(w = sample(1:4000, size = 8, replace = TRUE), v = runif(n = 8, 0, 10000)) knapsack_objects ``` ``` ## w v ## 1 1393 5908.8963 ## 2 2068 8363.7625 ## 3 2059 597.1862 ## 4 3782 1484.0430 ## 5 2096 2620.9358 ## 6 3979 3297.8963 ## 7 2554 2930.1486 ## 8 2858 6675.7049 ``` ```r brute_force_knapsack(knapsack_objects, 3500) ``` ``` ## $value ## [1] 14272.66 ## ## $elements ## [1] 1 2 ``` --- # Problem placakowy II ```r knapsack_objects10 = data.frame(w = sample(1:4000, size = 10, replace = TRUE), v = runif(n = 10, 0, 10000)) knapsack_objects14 = data.frame(w = sample(1:4000, size = 14, replace = TRUE), v = runif(n = 14, 0, 10000)) knapsack_objects18 = data.frame(w = sample(1:4000, size = 18, replace = TRUE), v = runif(n = 18, 0, 10000)) ``` ```r system.time(brute_force_knapsack(knapsack_objects10, 3500)) ``` ``` ## user system elapsed ## 0.120 0.000 0.206 ``` ```r system.time(brute_force_knapsack(knapsack_objects14, 3500)) ``` ``` ## user system elapsed ## 1.768 0.004 1.878 ``` ```r system.time(brute_force_knapsack(knapsack_objects18, 3500)) ``` ``` ## user system elapsed ## 29.292 0.060 29.760 ``` --- class: inverse, left, bottom # Dodatkowe informacje --- # Dodatkowe informacje - https://www.geeksforgeeks.org/greedy-algorithms/