如何通过memoization将这段回溯代码变成动态编程代码呢？

Question

我正在尝试学习动态规划，因此我正在尝试解决 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]);
            }
        }
    }
}

但我不知道在哪里或如何添加实际将最佳服装放在 DP 中位置 k 的部分 table。非常感谢任何帮助。

Answer 1

感谢@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]);
            }
        }
    }
}

如何通过memoization将这段回溯代码变成动态编程代码呢？

How to change this backtracking code into a dynamic programming code by using memoization?

c++

dynamic-programming

recursive-backtracking