背包
Eva.Q Lv9
2022-01-20 09:25:17

What makes the desert beautiful is that somewhere it hides a well.

0-1背包

个物品，书包体积为 ​ 。每个物品只能用一次。对于每个物品 分别表示物品的体积和价值。

状态定义：f[i][j] 表示 前 个物品总体积为 时的最大收益。

转移方程：f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
#define N 1007
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[1007][1007];
int v[1007], w[1007];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd();
    }
    int ans = 0;
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (j < v[i]) f[i][j] = f[i - 1] [j];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
            ans = max(ans, f[i][j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

因为初始化时 f[i][j] = 0 所以即使最后的总体积不到 ，我们也可以认为不到 的那部分体积用价值为 的物品填充好了，故最后答案可直接输出 f[n][m] 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
#define N 1007
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[1007][1007];
int v[1007], w[1007];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd();
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (j < v[i]) f[i][j] = f[i - 1] [j];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    printf("%d\n", f[n][m]);
    return 0;
}

压缩空间
滚动数组

因为我们在计算结果时只关心，该层上一层的答案是多少，故我们可用一个临时的一维数组保存下一层的答案。在计算完一层的答案后，将临时数组的值再赋值给数组 f 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
#define N 1007
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[1007], g[1007], v[1007], w[1007];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd();
    }
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (j < v[i]) g[j] = f[j];
            else g[j] = max(f[j], f[j - v[i]] + w[i]);
        }
        memcpy(f, g, sizeof(g));
    }
    printf("%d\n", f[m]);
    return 0;
}
压成一个一维数组

还可以发现，在计算某个位置时，我们只关心上一层小于等于当前位置的部分。故我们可以在一个一维数组里，选择从后往前更新，这样子也不会影响其他位置的计算结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
#define N 1007
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[1007], v[1007], w[1007];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd();
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= 0; --j) {
            if (j < v[i]) f[j] = f[j];
            else f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    printf("%d\n", f[m]);
    return 0;
}

完全背包

个物品，书包体积为 。每个物品能用无限次。对于每个物品 分别表示物品的体积和价值。

状态定义：f[i][j] 表示 前 个物品总体积为 时的最大收益。

转移方程：f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
#define N 1007
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[1007][1007], v[1007], w[1007];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd();
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (j < v[i]) f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
        }
    }
    printf("%d\n", f[n][m]);
    return 0;
}
压缩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
#define N 1007
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[1007], v[1007], w[1007];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd();
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (j < v[i]) f[j] = f[j];
            else f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    printf("%d\n", f[m]);
    return 0;
}

多重背包

个物品，书包体积为 。每个物品能用 次。对于每个物品 分别表示物品的体积和价值。

拆成一个一个

状态定义：f[i][j] 表示 前 组物品总体积为 时的最大收益。

转移方程： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[1007], v[1007], w[1007], l[1007];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd(); l[i] = rd();
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int k = 1; k <= l[i]; ++k)
            for (int j = m; j >= 0; --j) {
                if (j < v[i]) f[j] = f[j];
                else f[j] = max(f[j], f[j - v[i]] + w[i]);
            }
    }
    printf("%d\n", f[m]);
    return 0;
}
二进制拆分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
#define N 1007
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[2007], v[2007], w[2007], l[2007];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd(); l[i] = rd();
    }
    for (int i = 1; i <= n; ++i) {
        int res = l[i];
        for (int k = 1; k <= res; res -= k, k <<= 2) {
            int lim = v[i] * k, val = w[i] * k;
            for (int j = m; j >= lim; --j)
               f[j] = max(f[j], f[j - lim] + val);
        }
        int lim = v[i] * res, val = w[i] * res;
        for (int j = m; j >= lim; --j)
            f[j] = max(f[j], f[j - lim] + val);
    }
    printf("%d\n", f[m]);
    return 0;
}
单调队列
引入

是尾指针， 是头指针。

表示当前队列里的各个生物的攻击力。 表示队列里的各个生物的消失时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int c[100007][2], a[100007], b[100007];


int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        a[i] = rd(); b[i] = rd();
    }
    int k = 0, l = 1;
    for (int i = 1; i <= n; ++i) {
        for (; k >= l && b[i] >= c[k][0]; --k);
        c[++k][0] = b[i]; c[k][1] = a[i];
        printf("%d\n", c[l][0]);
        for(; k >= l && c[l][1] == i; ++l);
    }
    return 0;
}

优化背包

状态定义：f[i][j] 表示 前 组物品总体积为 时的最大收益。

转移方程：

没学会，等Co老师教我……

分组背包

物品属于不同的组，每一个组里只能取一个物品，每个物品只能用一次。

状态定义：f[i][j] 表示 前 组物品总体积为 时的最大收益。

转移方程： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[1007][1007], a[1007], v[1007], w[1007];
vector<int> c[1007];


int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        a[i] = rd(); v[i] = rd(); w[i] = rd();
        c[a[i]].push_back(i);
    }
    for (int i = 1; i <= 1000; ++i) {
       for (int j = 0; j <= m; ++j) {
           f[i][j] = f[i - 1][j];
           for (auto k : c[i]) 
               if (v[k] <= j)
                   f[i][j] = max(f[i][j], f[i - 1][j - v[k]] + w[k]);
       }
    }
    printf("%d\n", f[1000][m]);
    return 0;
}

压缩

跟0-1背包同理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[1007], a[1007], v[1007], w[1007];
vector<int> c[1007];


int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        a[i] = rd(); v[i] = rd(); w[i] = rd();
        c[a[i]].push_back(i);
    }
    for (int i = 1; i <= 1000; ++i)
       for (int j = m; j; --j)
           for (auto k : c[i]) 
               if (v[k] <= j)
                   f[j] = max(f[j], f[j - v[k]] + w[k]);
    printf("%d\n", f[m]);
    return 0;
}

二维背包

不仅有体积限制，还有体力限制，每个物品只能用一次。

状态定义：f[i][j][k] 表示 前 个物品，总体积为 ，消耗总体力为 时的最大收益。

转移方程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[107][107][107], t[107], v[107], w[107];


int main() {
    int n = rd(), m = rd(), k = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd(); t[i] = rd();
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            for (int x = 0; x <= k; ++x) {
                f[i][j][x] = f[i - 1][j][x];
                if (v[i] <= j && t[i] <= x)
                    f[i][j][x] = max(f[i][j][x], f[i - 1][j - v[i]][x - t[i]] + w[i]);
            }
        }
    }
    printf("%d\n", f[n][m][k]);
    return 0;
}

压缩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int f[107][107], t[107], v[107], w[107];


int main() {
    int n = rd(), m = rd(), k = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd(); t[i] = rd();
    }
    for (int i = 1; i <= n; ++i)
        for (int j = m; j >= v[i]; --j)
            for (int x = k; x >= t[i]; --x)
                    f[j][x] = max(f[j][x], f[j - v[i]][x - t[i]] + w[i]);
    printf("%d\n", f[m][k]);
    return 0;
}

  • Post title：背包
  • Post author：Eva.Q
  • Create time：2022-01-20 09:25:17
  • Post link：https://qyy/2022/01/20/Algorithm/DP1/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.