---

#include <iostream>
using namespace std;

int main()
{
    int w[] = {3, 2, 4, 1, 3, 1};      // веса
    int v[] = {55, 80, 60, 45, 105, 50}; // стоимости

    int n = sizeof(v) / sizeof(int);   // количество предметов
    int p = 9;                         // вместимость рюкзака

    int i, j;

    // создаём таблицу (n+1) x (p+1)
    int** c = new int*[n + 1];
    for (i = 0; i <= n; i++)
        c[i] = new int[p + 1]();

    // заполнение таблицы динамики
    for (i = 1; i <= n; i++)
    {
        for (j = 0; j <= p; j++)
        {
            if (w[i - 1] <= j)
            {
                c[i][j] = max(c[i - 1][j], c[i - 1][j - w[i - 1]] + v[i - 1]);
            }
            else
            {
                c[i][j] = c[i - 1][j];
            }
        }
    }

    // вывод таблицы
    cout << "Таблица динамики:\n";
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= p; j++)
            cout << c[i][j] << "\t";
        cout << endl;
    }

    cout << "\nМаксимальная стоимость = " << c[n][p] << endl;

    // восстановление выбранных предметов
    cout << "Выбранные предметы:\n";
    j = p;
    for (i = n; i > 0; i--)
    {
        if (c[i][j] != c[i - 1][j])
        {
            cout << "Предмет " << i 
                 << " (вес = " << w[i - 1] 
                 << ", стоимость = " << v[i - 1] << ")\n";
            j -= w[i - 1];
        }
    }

    // освобождение памяти
    for (i = 0; i <= n; i++)
        delete[] c[i];
    delete[] c;

    return 0;
}