何以包邮，动态规划，回溯出现错误

Question

csp-何以包邮：回溯错误

本人动态规划初学者，搞定01背包问题后尝试解决何以包邮的问题，并且成功解决了问题，得到了100分，但是我想通过回溯来确定选择的商品，却始终得到错误答案。

这是没有加回溯的代码，得到了满分

#include<iostream>
using namespace std;

int min(int a, int b) {
    if (a >= b)
        return b;
    else
        return a;
}

int dp[31][300001] = { 0 };

int main() {
    int n, P;
    cin >> n >> P;
    int p[31];
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    for(int i=0;i<=n;i++){
        for (int c = 0; c <= P; c++) {
            if (i == 0 && c == 0)
                dp[i][c] = 0;
            else if (i == 0 && c != 0)
                dp[i][c] = 300002;
            else if (i != 0 && c == 0)
                dp[i][c] = 0;
            else {
                int m1 = dp[i - 1][c];
                int m2;
                if (c - p[i] > 0)   //注意该特殊情况的处理（易错）
                    m2 = dp[i - 1][c - p[i]] + p[i];
                else 
                    m2 = p[i];
                dp[i][c] = min(m1, m2);
            }
        }
    }
    cout << dp[n][P] << endl;
    return 0;
}

这是添加了回溯的代码

//csp：何以包邮
#include<iostream>
using namespace std;

int dp[31][300001] = { {0} };
int rec[31][300001] = { {0} };

int main() {
    int n, P;
    cin >> n >> P;
    int p[31];
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    for(int i=0; i <= n; i++){
        for (int c = 0; c <= P; c++) {
            if (i == 0 && c == 0) {
                dp[i][c] = 0;
                rec[i][c] = 0;
            }
            else if (i == 0 && c != 0)
                dp[i][c] = 300002;
            else if (i != 0 && c == 0)
                dp[i][c] = 0;
            else {
                int m1 = dp[i - 1][c];
                int m2;
                if (c - p[i] > 0) 
                    m2 = dp[i - 1][c - p[i]] + p[i];
                else 
                    m2 = p[i];

                if (m1 >= m2) {  //填表以+记录追踪
                    dp[i][c] = m2;
                    rec[i][c] = 1;
                }
                else {
                    dp[i][c] = m1;
                    rec[i][c] = 0;
                }
            }
        }
    }
    cout << dp[n][P] << endl;
    //追踪
    cout << "选择的商品是：";
    for (int i = n, c = P; i > 0 && c > 0;) {
        if (rec[i][c] == 1) {
            cout << i<<' ';
            i -= 1;
            c -= p[i];
        }
        else {
            i -= 1;
        }
    }
    return 0;
}

拿csp中第一个用例来说

此处，选择的商品应该是：3 1，没有2，然后我把判断商品是否选择的数组全部输出来，结果四个全是1，希望大家可以看一下，指出我的错误与不足之处。

Answer 1

问题在于你在回溯过程中没有按照动态规划状态转移方程进行转移。

在你的代码中，你使用了 rec 数组来记录是否选择了某件物品，如果 rec[i][c] = 1，表示第i件物品已经被选择。
但是当你选择转移 dp[i][c] = dp[i - 1][c - p[i]] + p[i] 时，rec[i][c] = rec[i - 1][c - p[i]] + 1，这是错误的，因为 dp[i][c] 来自 dp[i-1][c-p[i]] + p[i] ，这个状态之前并没有选择第 i 个物品，而你在 rec 数组里给它加了1，就导致了错误的结果。

正确的做法是在计算 dp[i][c] 时，如果 dp[i][c] = dp[i-1][c-p[i]] + p[i],则 rec[i][c] = 1，如果dp[i][c] = dp[i-1][c],则 rec[i][c] = rec[i-1][c]。回溯的时候从后往前枚举，如果 rec[i][c] = 1,表示第i个物品被选择，那么就输出这个物品的编号并且更新c = c - p[i], i = i -1,继续枚举直到c = 0.

修改后的代码如下:

#include<iostream>
using namespace std;

int dp[31][300001] = { {0} };
int rec[31][300001] = { {0} };

int main() {
    int n, P;
    cin >> n >> P;
    int p[31];
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    for(int i=0; i <= n; i++){
        for (int c = 0; c <= P; c++) {
            if (i == 0 && c == 0) {
                dp[i][c] = 0;
                rec[i][c] = 0;
            }
            else if (i == 0 && c != 0)
                dp[i][c] = 300002;
            else if (i != 0 && c == 0)
                dp[i][c] = 0;
            else {
                int m1 = dp[i - 1][c];
                int m2;
                if (c - p[i] > 0) 
                    m2 = dp[i1][c - p[i]] + p[i];
else
m2 = p[i];


          if (m1 >= m2) {
              dp[i][c] = m1;
              rec[i][c] = rec[i-1][c];
          }else{
              dp[i][c] = m2;
              rec[i][c] = 1;
          }
      }
  }
}
cout << dp[n][P] << endl;
int i = n,c = P;
while(c>0){
if(rec[i][c] == 1){
cout<<i<<" ";
c = c - p[i];
}
i--;
}
return 0;
}

这样就能够正确的输出你选择的商品编号了。