монет изменения, но только с 1 каждого номинала монеты

Question

Проблема в том:

алгоритм я придумал что-то вроде:

pair<bool, bitmask>[n][A] memo;  
// memo[i][j].first will be true if its possible to 
// use up to i-th denomination for amt j 
// memo[i][j].second will contain info on which 
// denominations are used 
for i = 0 to n: 
    for j = 1 to A: 
    if (i==j): C[i][j] = {true, {i}} 
    else if (C[i-1][j].first == true): C[i][j] = C[i-1][j]] 
    else if (...see recurrance relation...): 
     C[i][j] = {true, C[i-1][j]+{denom[i]}} 
    else: C[i][j] = false 

Правильно ли до сих пор? Но я не знаю, как я мог бы доказательство его правильности ... Моя попытка выглядит просто переписав код на английском ...

Для 1, если: мы всегда можем использовать 1 монету номиналом я решить amt = i. Для 1-го else if: если у нас есть решение для amt без с использованием текущего наименования, мы можем повторно использовать это решение. Для 2-го еще, если: если текущее наименование может быть использовано (< = АМТ), а наименование не используется, мы можем ...

Для сложности: Таблица имеет размер нА. И каждая ячейка занимает O (1) раз, чтобы заполнить. Может ли кто-нибудь помочь указать мне в правильном направлении?

Answer 1

Да, я бы сказал, что вы полностью на правильном пути здесь. Проблема, которую вы решаете, по сути является проблемой подмножества сумм, и ваше решение является стандартным динамическим программированием (см. http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution).

С точки зрения правильности, я бы сказал, что объяснение отношения повторения и базовых дел будет в порядке. Как стилистический момент, я бы не стал проходить через код и не оправдывал каждую строку, а скорее фокусировался на большой картине. Поэтому просто объясните, что представляет ваша таблица, и как вы можете настроить базовые случаи и отношения повторения, и читатель может легко просмотреть код и увидеть, что вы его реализовали.

Для выполнения: Да, ваш алгоритм просто перемещается по элементам таблицы и заполняет их, чтобы ваше объяснение было правильным.