01背包
每个物品要么拿要么不拿

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

using namespace std;

const int N = 1010;
int f[N], v[N], w[N];
int n, V;

int main()
{
    scanf("%d%d", &n, &V);
    for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);
    
    for(int i = 1; i <= n; i++)
        for(int j = V; j >= v[i] ; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[V];
}

完全背包
每个物品能拿无限个

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

using namespace std;

const int N = 1010;
int f[N], v[N], w[N];
int n, V;

int main()
{
    scanf("%d%d", &n, &V);
    for(int i = 1; i <= n ;i++) scanf("%d%d", &v[i], &w[i]);
    
    for(int i = 1; i <= n ;i ++)
        for(int j = v[i] ; j <= V ; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[V];
}

多重背包
每个物品有限个
时间复杂度O(N$\times$V$\times$S) S = $\sum s_i$

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

using namespace std;

const int N = 110;
int f[N];
int n,vv;

int main()
{
    scanf("%d%d", &n, &vv);
    
    for(int i = 1 ;i <= n; i++)
    {
        int v,w,s;
        scanf("%d%d%d", &v, &w, &s);
        for(int k = 1 ; k <= s ; k++)
            for(int j = vv; j >= v; j--)
             f[j] = max(f[j], f[j - v] + w);
    }
    cout << f[vv];
}

多重背包
时间复杂度O(N$\times$V$\times$log(S)) S = $\sum s_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
#include <cstring>
#include <iostream>
using namespace std;

const int N = 2010;
int f[N];
int n, v;

int main() {
    scanf("%d%d", &n, &v);
    for (int i = 1; i <= n; i++) {
        int vv, ww, s;
        scanf("%d%d%d", &vv, &ww, &s);
        if (s < 0) s = -s;
        for (int j = 1; j <= s; j *= 2) {
            s -= j;
            for (int k = v; k >= j * vv; k--) {
                f[k] = max(f[k], f[k - j * vv] + j * ww);
            }
        }
        if (s > 0) {
            for (int k = v; k >= s * vv; k--) {
                f[k] = max(f[k], f[k - s * vv] + s * ww);
            }
        }
    }
    cout << f[v] << endl;
}