动态规划

动态规划（Dynamic Programming）是一种用来解决一类最优化问题的算法思想，属运筹学的内容。简单来说，动态规划就是将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。需要注意的是，动态规划会将每个求解过的子问题的解记录下来，这样当下次碰到相同的子问题时，就可以直接使用之前记录的结果，而不是重复计算。

关键：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划（DP）。

核心：如何设计状态和状态转移方程。

动态规划初步

0-1背包问题

问题描述

有 N 件物品和一个最多能被重量为 W 的背包。第 i 件物品的重量是$weight_i$，得到的价值是 $value_i$ 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

代码

const int N = 1e4 + 5;
int dp[N][N], w[N], v[N];//w数组存储物品重量 v数组存储物品价值
int main() {
    int n, m;//物品数量 背包容量
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);//核心递推式    
            }
            else dp[i][j] = dp[i - 1][j];
        }
    }
    cout << "max=" << dp[n][m] << endl;
    return 0;
}

观察核心递推式，可发现每一行的dp都利用到了上一行的dp值（dp[ i-1 ][ j ]），除此之外再往上的值就没有用到，故可以利用这个性质，将dp数组压成一维处理，注意遍历的时候需要逆序处理。

const int N = 1e4 + 5;
int dp[N], w[N], v[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);//逆序更新dp数组，因为dp[j]依赖于dp表左上方的值来进行更新
        }
    }
    cout << "max=" << dp[m] << endl;
   return 0;
}

完全背包问题

问题描述

有 N 件物品和一个最多能被重量为 W 的背包。第 i 件物品的重量是$weight_i$，得到的价值是 $value_i$ 。每件物品可以用无数次，求解将哪些物品装入背包里物品价值总和最大。

代码

const int N = 1e4 + 5;
int dp[N][N];
int w[N], v[N];//w数组存放重量，v数组存放价值
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);/*核心递推式 与0-1背包区别是dp[i][j-w[i]]+v[i]，而0-1背包是dp[i-1][j-w[i]]+v[i]*/
            }
            else dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

同理，我们使用一维数组可以进行空间优化，注意这次我们可以直接正序遍历。

const int N = 1e4 + 5;
int dp[N];
int w[N], v[N];//质量 价值
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = w[i]; j <= m; j++) {//注意了，这里的j是从小到大枚举，和01背包不一样,01背包必须逆序
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << "maxn=" << dp[m] << endl;
    return 0;
}