Qwe1
Ладно. Рассмотрим всё по порядку. Пусть у нас есть m целых положительных элементов a[i] и трубеится найти можно ли из них составить сумму равную n. Создадим массив can[i][k] размера m на n+1. can[i][k] = 1, если мы можем получить каким-то образом суммируя только элементы a[0]...a[i] сумму равную k. Нас интерисует значение can[m][n], т.е. можем ли мы получить используя элементы a[0]...a[m] сумму n.
Очевидно can[0][k] = 0, для всех k != a[0] и k != 0. can[0][0] = 1 и can[0][a[0]] = 1. Т.е. используя один элемент мы можем получить только сумму равную 0 или этому элементу.
Рассмотрим как по массиву can[i-1] можно построить can[i]. Очевидно, что используя i элементов всегда можно получить те же суммы, что и используя i=1 элемент (просто не добавляя к прежним суммам i-й элемент). Т.е. если can[i-1][k]=1, то can[i][k]=1 так же. Кроме того, к любой из прежних сумм мы можем добавить i-й элемент, т.е. если can[i-1][k]=1, то can[i][k+a[i]]=1 так же. Во всех остальных случаях can[i][k]=0.
Реализация вышеописанного в (псевдо)коде будет выглядеть вот так:
Код:
int can[m][max_sum+1], i, j;
for (i = 0; i < m; ++i)
for (j = 0; j <= max_sum; ++j)
can[i][j] = 0;
can[0][0] = can[0][a[0]] = 1;
for (i = 1; i < m; ++i)
{
for (j = 0; j < max_sum; ++j)
can[i][j] = can[i-1][j];
for (j = 0; j < max_sum; ++j)
if (can[i-1][j])
can[i][j+a[j]] = 1;
}
Пользуясь тем фактом, что у нас в can[i] по сравнению с can[i-1] только дописываются единички, а так же тем, что все элементы мы можем модифицировать массив прям на месте, вместо того, что бы иметь цепочку массивов can[0]...can[m].
Вот так:
Код:
int can[max_sum], i, j;
for (i = 0; i <= max_sum; ++i)
can[i] = 0;
can[0] = 1;
for (i = 0; i < m; ++i)
for (j = max_sum; j > 0; --j)
if (j >= a[i] && can[j-a[i]])
can[j] = 1;
В результате can[n] = 1, если можно получить сумму равную n.
Теперь, если вместо 1 в can[k] ставить то, число которое мы добавили для получения суммы k, то можно будет получить список всех чисел, которые необходимо было просуммировать.
b1 = can[k] - первое число
b2 = can[k-b1] - второе число
b3 = can[k-b1-b2] - третье число
b4 = can[k-b1-b2-b3] - четвёртое число.
итд
В коде это будет так:
Код:
printf("Всё хорошо, путь:\n");
for (i = n; i != 0; i -= way[i])
printf("%d\n", way[i]);
