Стиральная машина Проб

Question

Я пытаюсь решить следующую проблему DP следующим образом:

Сотрудник компании, занимающейся мойкой автомобилей, преследует цель мыть общее количество автомобилей C в течение следующих D дней. Из-за ограничений в его расписании и поставках он может мыть машины не более D _i автомобилей в день. К счастью для него, он предоставил ему список максимального количества автомобилей, которые он может мыть каждый день в течение D дней заранее, так что [День 1 = 2 машины, День 2 = 3 машины, День 3 = 4 машины ). Сколько разных способов он может достичь своей цели - мыть машины C в течение D дней, чтобы сумма всех автомобилей за эти дни равнялась C. Он должен мыть не менее 1 машины в день. Он не может достичь своей цели через # дней

Answer 1

Примечание: проблема та же, что и у другой распространенной проблемы: сколько существует способов бросить определенную сумму, используя кости с d1, d2, d3, ..., dn сторон.

Если есть C[n, i] способов мойки n автомобилей за i дней, есть сумма (C [nk], i + 1), k = 1..D [i + 1]) способов мойки n автомобилей за i + 1 день.С краевыми условиями: C [0, 0] = 1, C [0, _] = 0.

Это непосредственно дает этот алгоритм O (Cmax (D) | D |), который использует O (C) пробел.

def cars(C, D):
    r = [1] + [0] * C
    for d in D:
        for i in range(C, -1, -1):
            r[i] = sum(r[j] for j in range(max(0, i-d), i))
    return r[C]

print(cars(5, [2, 3, 4]))

Вы можете сделать немного лучше, поскольку внутренний цикл выполняет скользящую сумму значений d, которые могут быть вычислены за O (1) раз в среднем на элемент C.

def cars(C, D):
    r = [1] + [0] * C
    for d in D:
        S = 0
        for i in range(C, -d-1, -1):
            if i >= 0:
                S += r[i]
            if i + d <= C:
                S -= r[i+d]
                r[i+d] = S
    return r[C]

print(cars(5, [2, 3, 4]))

Поскольку без ограничения общности max (D)

Если это помогает, этокод по существу вычисляет первые C + 1 члены полинома P [D [0]] * P [D [1]] * ... * P [D [len (D) -1]], где P [d] = х + х ^ 2 + ... + х ^ д.Коэффициент x ^ C в результате является решением вашей проблемы.

Answer 2

Вот решение динамического программирования, которое работает за O(D*C*C) время;

Пример матрицы для D = 3, C до 10 с пределами [2, 3, 4].

int NumberOfWays(int c, int d, int[] limits)
{
    // let's t[i, j] be amount of ways j cars can be washed in i days

    var t = new int[d + 1, c + 1];

    for (int day = 1; day <= d; day++)
    {
        int dayLimit = limits[day - 1];

        for (int cars = day; cars <= c; cars++)
        {
            if (day == 1) // first day
            {
                if (cars <= dayLimit)
                    t[day, cars] = 1;
            } else // not first day
            {
                // okay, number of ways given amount of cars can be washed
                // on certain day can be calculated using amounts possible on the previous day

                for (int carsOnPrevDay = 1; carsOnPrevDay < cars; carsOnPrevDay++)
                {
                    if (cars - carsOnPrevDay > dayLimit)
                        continue; // day limit exceeded

                    t[day, cars] += t[day - 1, carsOnPrevDay];
                }
            }
        }
    }

    return t[d, c];
}

Answer 3

На более заметной ноте я попытался вручную выполнить ваш алгоритм (игнорируя ограничивающие проблемы) и получил эту матрицу:

Но вы, вероятно, ищете больше для этого (обратите внимание, что я забыл заполнить недопустимые значения из-за лени):

Обратите внимание на то, чтобы немного подстроить суммирование, особенно в первый день, когда по какой-то причине невозможно вымыть 2 или 3 машины. После этого вы правы, вернув OPT[D, C].