Продолжаю слушать курс Algorithmic Toolbox.
Прослушал блок про оптимальную загрузку рюкзака жадным алгоритмом, и начал писать код для поиска оптимальной загрузки рюкзака (Fractional Knapsack).
Условия:
- Ввод и вывод данных через терминал.
- Результат поиска - максимальная стоимость продуктов в рюкзаке.
- Тестирующий код - отдельный процесс.
Часть 1 - первая реализация
Поиск максимальной стоимости сделал на OCaml. Ввод данных идёт в stdin
в таком виде:
вместительность_рюкзака количество_продуктов [общая_цена вес]* 7 3 20 4 14 2 18 3
let find_solution capacity items = let rec _solve free_capacity sorted_items = match sorted_items with | [] -> 0.0 | (price, weight) :: tl -> if weight <= free_capacity then price +. (_solve (free_capacity -. weight) tl) else price /. weight *. free_capacity in List.sort (fun (p1, w1) (p2, w2) -> compare (p2 /. w2) (p1 /. w1)) items |> _solve capacity let () = let knapsack_capacity = Scanf.scanf " %f" (fun x -> x) in let number_of_items = Scanf.scanf " %d" (fun x -> x) in (* [(price, weight)] *) let rec scan_pairs = function | 0 -> [] | n -> Scanf.scanf " %f %f" (fun a b -> (a, b)) :: scan_pairs (n - 1) in let items = scan_pairs number_of_items in find_solution knapsack_capacity items |> string_of_float |> print_endline;
Проверку решения сделал на Python. Алгоритм поиска максимальной стоимости рюкзака в этом случае сделал итеративным, а не рекурсивным, как в случае с OCaml.
#!/usr/bin/env python # -*- coding: utf-8 -*- 'Тест для проверки корректности решения загрузки рюкзака порграммой на OCaml.' import random from subprocess import check_output def solve(capacity, pairs): pairs = sorted(pairs, key=lambda x: x[0] / x[1], reverse=True) value = 0 while capacity and pairs: (price, weight), *pairs = pairs if capacity < weight: value += (price / weight) * capacity capacity = 0 else: value += price capacity -= weight return value def main(): random.seed(1) for number_of_pairs in range(15): capacity = random.randint(3, 30) pairs = [(random.randint(1, 20), random.randint(1, 20)) for _ in range(number_of_pairs)] test_data = '{capacity} {number_of_pairs} {pairs}'.format( capacity=capacity, number_of_pairs=number_of_pairs, pairs=' '.join(['{} {}'.format(*i) for i in pairs]) ) ocaml_result = check_output( './fractional_knapsack.ml.byte', input=bytes(test_data, 'utf-8')) py_result = solve(capacity, pairs) print(float(ocaml_result) == py_result, '[p {}, o {}]'.format(py_result, ocaml_result), test_data) if __name__ == '__main__': main()
И результат:
True [p 0, o b'0.\n'] 7 0 True [p 3, o b'3.\n'] 21 1 3 9 False [p 7.384615384615385, o b'7.38461538462\n'] 6 2 16 15 16 13 True [p 36, o b'36.\n'] 28 3 7 4 16 1 13 14 True [p 39.6, o b'39.6\n'] 22 4 1 15 9 8 19 4 11 1 True [p 1.6, o b'1.6\n'] 3 5 1 18 1 13 7 14 1 17 8 15 False [p 40.77777777777778, o b'40.7777777778\n'] 18 6 18 8 12 8 8 15 10 1 14 18 4 6 False [p 27.647058823529413, o b'27.6470588235\n'] 23 7 10 4 11 17 14 17 7 10 10 19 16 17 13 19 False [p 50.05882352941177, o b'50.0588235294\n'] 30 8 2 16 8 13 14 6 12 18 12 3 15 17 4 6 17 13 False [p 62.333333333333336, o b'62.3333333333\n'] 14 9 16 1 16 2 10 20 19 19 13 6 6 17 8 1 7 18 18 8 False [p 33.583333333333336, o b'33.5833333333\n'] 15 10 17 12 19 12 15 9 18 20 1 13 17 5 17 18 7 14 2 16 12 19 True [p 55.0, o b'55.\n'] 20 11 7 17 14 16 12 14 12 1 18 18 20 20 11 15 20 1 8 6 18 19 6 3 True [p 83.2, o b'83.2\n'] 28 12 18 9 2 3 3 1 15 1 9 8 9 4 20 6 12 10 3 6 6 9 17 6 9 10 True [p 64.0, o b'64.\n'] 17 13 11 16 16 4 1 10 13 11 14 7 9 4 9 17 7 20 14 1 8 1 13 5 2 6 15 17 True [p 61.0, o b'61.\n'] 24 14 14 18 8 17 15 8 17 1 13 19 11 14 2 10 5 7 2 10 3 3 10 10 6 14 19 9 5 1
Почти сработало. Осталось доделать тест, чтобы он мог обрабатывать расхождение в точности представления чисел с плавающей запятой. На этом мой день закончился, и я отложил доработки до следующего дня.
Часть 2 - доработки
Полученное решение меня не устраивало по нескольким пунктам:
- нет хвостовой рекурсии в коде на OCaml;
- нет округления в проверке равенства результатов;
- вывод всех тестовых данных в коде на Python, в то время как мне нужно было видеть только ошибки.
Для начала я сделал так, чтобы в рекурсивном поиске решения последним действием был вызов функции. В таком виде рекурсия может быть преобразована в хвостовую.
let find_solution capacity items = let rec _solve free_capacity value sorted_items = match sorted_items with | [] -> value | (price, weight) :: tl -> if weight <= free_capacity then _solve (free_capacity -. weight) (value +. price) tl else value +. price /. weight *. free_capacity in List.sort (fun (p1, w1) (p2, w2) -> compare (p2 /. w2) (p1 /. w1)) items |> _solve capacity 0.0 let () = let knapsack_capacity = Scanf.scanf " %f" (fun x -> x) in let number_of_items = Scanf.scanf " %d" (fun x -> x) in (* [(price, weight)] *) let rec scan_pairs = function | 0 -> [] | n -> Scanf.scanf " %f %f" (fun a b -> (a, b)) :: scan_pairs (n - 1) in let items = scan_pairs number_of_items in find_solution knapsack_capacity items |> string_of_float |> print_endline;
Потом настал черёд тестового скрипта на Python. Я прикинул, что трёх знаков после запятой мне хватит для точности сравнения.
import random from subprocess import check_output def solve(capacity, pairs): pairs = sorted(pairs, key=lambda x: x[0] / x[1], reverse=True) value = 0 while capacity and pairs: (price, weight), *pairs = pairs if capacity < weight: value += (price / weight) * capacity capacity = 0 else: value += price capacity -= weight return value def main(): random.seed(1) for number_of_pairs in range(1000): capacity = random.randint(3, 30) pairs = [(random.randint(1, 20), random.randint(1, 20)) for _ in range(number_of_pairs)] test_data = '{capacity} {number_of_pairs} {pairs}'.format( capacity=capacity, number_of_pairs=number_of_pairs, pairs=' '.join(['{} {}'.format(*i) for i in pairs]) ) ocaml_result = check_output( './fractional_knapsack.ml.byte', input=bytes(test_data, 'utf-8')) ocaml_result = float(ocaml_result) py_result = solve(capacity, pairs) precise = 3 ocaml_result = round(ocaml_result, precise) py_result = round(py_result, precise) assert ocaml_result == py_result, ('[p {}, o {}] {}'.format( py_result, ocaml_result, test_data)) print('Все тесты пройдены.') if __name__ == '__main__': main()
Запущенный скрипт показал нужное "Все тесты пройдены.".