Часть 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()

Запущенный скрипт показал нужное "Все тесты пройдены.".