8. 二维费用的背包问题

01 背包，二维费用

二维费用的背包问题 DP 分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

int n, v, m;
const int N = 110;
int f[N][N];

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

278. 数字组合

01 背包求方案数

求方案数，状态表示用“恰好”

数字组合 DP 分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;

const int N = 10010;

int f[N], a[110];
int n, m;

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

1019. 庆功会

多重背包朴素版应用。

时间复杂度为 O(n * m * s)，n 为物品种数，m 为背包最大容量，s 为每种物品的最大数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

const int N = 6010;
int f[N];
int n, m;

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

1023. 买书

完全背包求方案数

求方案数，状态表示用“恰好”

买书 DP 分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

const int N = 1010;

int v[4] = {10, 20, 50, 100};
int f[N];

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