Как превратить этот код возврата в динамический программный код, используя памятку? - PullRequest
Новая
       14

Как превратить этот код возврата в динамический программный код, используя памятку?

1 голос
/ 12 июня 2019

Я пытаюсь научиться динамическому программированию и, следовательно, я пытаюсь решить UVA 11450 .Поскольку я знаю, что могу решить этот вопрос с помощью обратного отслеживания, я решил решить его с помощью обратного отслеживания, а затем добавить памятку в код.Однако я не могу этого сделать.

Вот код комментария без напоминания: 

#include <bits/stdc++.h>

using namespace std;


bool b;                         // this tells us if a solution is found or not
int c;                          // store input c
vector <vector <int>> arr;     // declare a global array to store the type and cost of the garments


int money = INT_MAX;           // these two fields store the most optimal solution found so far
vector <int> garr;


// this function fills 'c' - the candidates for the k'th postition
void construct_candidates(vector <int> &a, int k, int m, vector<int> &c)        
{
    for (int i: arr[k])
    {
        if (i <= m ) c.push_back(i);    // if cost of the model 'i' of garment 'k' is less than or equal to money remaining,
    }                                   // put it in array 'c'.
}


void backtrack(vector <int> &a, int k, int m)
{
    vector <int> c;                     // this array stores the candidates for postion k.

    if (k == a.size() - 1)              // if (is_a_soln) process_solution
    {
        if (m < money)
        {
            b = true;
            money = m;
            garr = a;
        }
    }
    else                                // else backtrack with updated parameters
    {
        k++;
        construct_candidates(a, k , m, c);
        for (int i = 0; i < c.size(); i++)
        {
            a[k] = c[i];
            backtrack(a, k, m - c[i]);
        }
    }
}


int main()
{

    int n;
    cin >> n;
    while (n--)
    {   
        b = false;                              // initialising global variables
        money = INT_MAX;
        arr.clear();
        int m;
        cin >> m >> c;
        arr = vector <vector <int>>(c);

        for(int i = 0; i < c; i++)              // storing the input in arr
        {
            int k;
            cin >> k;
            arr[i] = vector <int> (k);
            for (int j = 0; j < k; j++)
            {
                cin >> arr[i][j];
            }
        }

        vector <int> a(c, -1);         // the backtracking code will attempt 
                                       //to fill this array with optimal garments

        backtrack(a, -1, m);                      

        if (b) cout <<m - money << endl;
        else cout << "no solution" << endl;
    }

    return 0;
}

Теперь, чтобы добавить памятку, я попытался сделать: 

vector <vector <int>> dp(20, vector<int> (201, -1));
void backtrack(vector <int> &a, int k, int m)
{
    if (dp[k][m] != -1)                    // this is
    {                                      // the 
        k++;                               // part
        a[k] = dp[k][m];                   // that 
        backtrack(a, k, m - a[k]);         // is
    }                                      // added
    else
    {
        vector <int> c;                    

        if (k == a.size() - 1)              
        {
            if (m < money)
            {
                b = true;
                money = m;
                garr = a;
            }
        }
        else                                
        {
            k++;
            construct_candidates(a, k , m, c);
            for (int i = 0; i < c.size(); i++)
            {
                a[k] = c[i];
                backtrack(a, k, m - c[i]);
            }
        }
    }
}

Но я не знаю, где иликак добавить деталь, которая фактически помещает оптимальный предмет одежды в позицию k в таблице DP.Любая помощь очень ценится.

1 Ответ

0 голосов
/ 14 июня 2019

Благодаря очень полезному комментарию @AlexanderZhang я решил вопрос.Обратитесь к его комментарию для деталей, если интересно.Вот код: 

vector <vector <int>> dp(20, vector<int> (201, -1));
void backtrack(vector <int> &a, int k, int m)
{
    k++;
    if (dp[k][m] != -1)
    {
        return;
    }
    else
    {
        dp[k][m]++;
        vector <int> c;                     // this array stores the candidates for postion k.

//        for (int kj : a) cout << kj << " ";
//        cout << endl;

        if (k == a.size() )              // if (is_a_soln) process_solution
        {
            if (m < money)
            {
                b = true;
                money = m;
                garr = a;
            }
        }
        else                                // else backtrack with updated parameters
        {
//            k++;
            construct_candidates(a, k , m, c);
            for (int i = 0; i < c.size(); i++)
            {
                a[k] = c[i];
                backtrack(a, k, m - c[i]);
            }
        }
    }
}
...