Я пытаюсь найти и решить отношение повторяемости для подхода динамического программирования к UVA # 11450. В качестве оговорки, это часть домашнего задания, которое я в основном выполнил, но меня не смущает анализ.
Вот мой (рабочий) код:
int shop(int m, int c, int items[][21], int sol[][20]) {
if (m < 0) return NONE; // No money left
if (c == 0) return 0; // No garments left
if (sol[m][c] != NONE) return sol[m][c]; // We've been here before
// For each model of the current garment
for (int i = 1; i <= items[c-1][0]; i++) {
// Save the result
int result = shop(m-items[c-1][i], c-1, items, sol);
// If there was a valid result, record it for next time
if (result != NONE) sol[m][c] = max(sol[m][c], result+items[c-1][i]);
}
return sol[m][c];
}
У меня проблемы с несколькими аспектами анализа:
- Какая основная операция? Моей первой реакцией было бы вычитание, поскольку каждый раз, когда мы вызываем функцию, мы вычитаем единицу из C.
- Поскольку рекурсивный вызов находится внутри цикла, означает ли это просто умножение в рекуррентном отношении?
- Как учесть тот факт, что он использует динамическую таблицу в отношении повторения? Я знаю, что некоторые проблемы распадаются на линейные при использовании таблицы, но я не уверен, как она распадается.
Я знаю, что сложность (согласно Algorithmist) составляет O (M * C * max ( K)), где K - количество моделей каждого предмета одежды, но я изо всех сил пытаюсь работать в обратном направлении, чтобы получить рекуррентное соотношение. Вот моя догадка:
S(c) = k * S(c-1) + 1, S(0) = 0
Однако при этом M не учитывается.
Мысли?
