动态规划

基本分析思路：

状态表示（化零为整）
- 集合：依据经验中的类似解法，定义集合的表示形式。例如背包问题，统一是前i个物品不超过..(体积、重量)约束的选法
- 属性：求max/min/cnt
状态转移（化整为零）
- 划分依据；寻找最后一个不同点
- 保证不重不漏，如果是求min或者max可以允许重复
时空优化
- 例如01背包把f数组从二维降到一维

01背包

基础版本：二维数组

状态表示：用f[i][j]表示前i个物品中体积不超过j的最大价值，属性是max
状态转移：把集合分成两个部分：选择第i个物品和不选第i个物品，两者求max，可以验证是不重不漏的

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x7fffffff;
const int N = 1005;
const int mod = 1e9 + 7;

int n, m;
int v[N], w[N];
int f[N][N];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> v[i] >> w[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      f[i][j] = f[i - 1][j];
      if (j >= v[i])
        f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
    }
  }
  cout << f[n][m] << endl;
  return 0;
}

时空优化，这个时间复杂度是不好优化的。空间上，需要降维的部分有两个：第一处

1	f[i][j] = f[i - 1][j];

这里由于i是从前往后递推的，所以可以降掉第一维

第二处：

1	f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);

这里我们可以看到j-v[i]一定是比j小的，所以我们在算前i个物品的时候，如果j是从大到小循环的话，计算f[i][j]的时候，j-v[i]还停留在前i-1个物品的计算结果，也就达到了降维的效果，可以统一把第一维删去。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x7fffffff;
const int N = 1005;
const int mod = 1e9 + 7;

int n, m;
int v[N], w[N];
int f[N];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> v[i] >> w[i];
  }
  for (int i = 1; i <= n; i++)
    for (int j = m; j >= 0; j--)
      if (j >= v[i])
        f[j] = max(f[j], f[j - v[i]] + w[i]);
  cout << f[m] << endl;
  return 0;
}

可以看到还是简化了不少的

完全背包

先上代码，可以看到结果就是上面01背包，j 递增遍历

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x7fffffff;
const int N = 1005;
const int mod = 1e9 + 7;

int n, m;
int v[N], w[N];
int f[N];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> v[i] >> w[i];
  }
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++)
      if (j >= v[i])
        f[j] = max(f[j], f[j - v[i]] + w[i]);
  cout << f[m] << endl;
  return 0;
}

状态转移方程：

// 01背包
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]);
// 完全背包
f[i][j] = max(f[i-1][j], f[i][j-v] + w);

这里中间有一步递推式需要说明

f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2*v]+2*w, ... , f[i-1][j-k*v]+k*w,.... );
f[i][j-v] = max(f[i-1][j-v], f[i-1][j-2*v]+w, f[i-1][j-3*v]+2*w, ... , f[i-1][j-k*v-v]+k*w, .. );
两者之间就差了一个w
所以可以修改为
f[i][j] = max(f[i-1][j], f[i][j-v]+w);
这样得到了状态转移方程

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x7fffffff;
const int N = 1005;
const int mod = 1e9 + 7;

int v[N], w[N];
int f[N][N];
int n, m;

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> v[i] >> w[i];
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      f[i][j] = f[i - 1][j];
      if (j >= v[i])
        f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
    }
  }
  cout << f[n][m] << endl;
  return 0;
}

时空优化：

这里可以看到当j递增循环的时候，j-v[i]<j，当算第i种物品时，j-v[i]一定在j前面先被计算。所以表现为j从小到大循环，最后输出f[m]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x7fffffff;
const int N = 1005;
const int mod = 1e9 + 7;

int v[N], w[N];
int f[N];
int n, m;

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> v[i] >> w[i];
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      if (j >= v[i])
        f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
  }
  cout << f[m] << endl;
  return 0;
}

Joseri的小站

简单动态规划问题

动态规划

01背包

完全背包