01背包

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

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<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 1010;
int n,m;
//前i个物体，总体积是j 的最大总价值
int f[MAXN][MAXN];
int V[MAXN],W[MAXN];
int main(){
    scanf("%d%d",&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-1][j-v[i]]过来。
                f[i][j] = max(f[i][j],f[i-1][j-V[i]]+W[i]);
            }
        }
    }
    int ans = 0;
    //在前n个物体中，选价值最大的一个
    for(int i = 0; i <= m; i++){
        ans = max(ans,f[n][i]);
    }
    printf("%d",ans);
    return 0;
}

一维数组优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int MAXN = 1010;
int f[MAXN];
int N,M;
int V[MAXN],W[MAXN];
int main(){
    scanf("%d%d",&N,&M);
    for(int i = 1; i <= N; i++) scanf("%d%d",&V[i],&W[i]);
    for(int i = 1; i <= N; i++)
        //从后往前推，保留i-1的状态
        for(int j = M; j >= V[i]; j--){
            f[j] = max(f[j],f[j-V[i]]+W[i]);
        }
    printf("%d",f[M]);
    return 0;
}

完全背包

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

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<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int N,M;
const int MAXN = 1010;
int f[MAXN][MAXN],V[MAXN],W[MAXN];
//转移方程，f[i][j] = max{f[i-1][j-k*V[i]+k*W[i]}
//含义：可以在之前选完后，选择当前的[M/V[i]]个，取价值最大的那个。
int main(){
    scanf("%d%d",&N,&M);
    for(int i = 1; i <= N; i++){
        scanf("%d%d",&V[i],&W[i]);
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            for(int k = 0; k * V[i] <= j; k++){
                f[i][j] = max(f[i][j],f[i-1][j-k*V[i]]+k*W[i]);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= M; i++){
        ans = max(ans,f[N][i]);
    }
    printf("%d",ans);
    return 0;
}

一维数组优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 1010;
int f[MAXN];
int N,M;
int main(){
    scanf("%d%d",&N,&M);
    for(int i = 1; i <= N; i++){
        int v,w;
        scanf("%d%d",&v,&w);
        //每一层考虑-->尽可能选取多的第i个背包后，最大的价值，所以直接从当前层的状态转移，表示选择0,1,...,k个的背包之后的价值。
        for(int j = v; j <= M; j++){
            f[j] = max(f[j],f[j-v]+w);
        }
    }
    printf("%d",f[M]);
    return 0;
}

多重背包：

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 110;
int dp[MAXN],N,M;
int main(){
    scanf("%d%d",&N,&M);
    for(int i = 1; i <= N; i++){
        int v,w,s;
        scanf("%d%d%d",&v,&w,&s);
        for(int j = M; j >= v; j--){
            //从1到s个背包都试着选一下。
            for(int k = 1; k <= s && k*v <= j; k++){
                dp[j] = max(dp[j],dp[j-k*v]+k*w);
            }
        }
    }
    printf("%d",dp[M]);
    return 0;
}

二进制思想优化：

因为每个背包可选s个，我们试着将其转化为0/1背包问题，把每个背包划分0~s种，去做0/1背包，发现问题的复杂度没有变，我们考虑每个物品都有选和不选两种情况，我们知道每一个数都可以有相应的二进制对应位作为2的幂相乘得到，所以我们将s拆分成二进制数位相乘。这样每一层做0/1背包，之前的结果没有浪费掉，是可以接着相加，并且最后得到s个，做到了从O(n)到O(logn)的优化。

这里有一个问题就是在log(s)时，如果s不是二的整数次幂，会计算到大于s的第一个整数次幂，这样结果就不对了，成了计算到了大于s的第一个整数次幂个数量。我们必须要将加到的数最大只会到s，这里有一个做法：先加到小于s的最大的二的整数次幂x，然后加上 s-x 就可以表示为 0~s这么多种方案了。举例：

1
2
3
4
5
6
10 = 0+ 1 + 2 + 4 + 3
0 ~ 7 = (0,1,2,4)的任意组合
8 = 5+3 //(0~7中的5)
9 = 6+3 //(0~7中的6)
10 = 7+3 //(0~7中的7)
并且求和只能取到10

所以该方法成立。

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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 2e6+10;
int dp[2020],V[MAXN],W[MAXN];
int main(){
    int t = 0;
    int n,m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        int v,w,s;
        cin >> v >> w >> s;
        for(int k = 1; k <= s; k *= 2){
            V[t] = v*k;
            W[t++] = w*k;
            s -= k;
        }
        if(s > 0) {
            V[t] = v*s;
            W[t++] = w*s;
        }
    }
    for(int i = 0; i < t ; i++){
        for(int j = m; j >= V[i]; j--){
            dp[j] = max(dp[j],dp[j-V[i]]+W[i]);
        }
    }
    cout << dp[m];
    return 0;
}

混合背包

有 N 种物品和一个容量是 V 的背包。

物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

  • si=−1 表示第 i 种物品只能用1次；
  • si=0 表示第 i 种物品可以用无限次；
  • si>0 表示第 i 种物品可以使用 si 次；

输出格式

输出一个整数，表示最大价值。

思路：

其实只是0-1背包（多重背包）和完全背包的组合版
每件物品该用完全背包解就用完全背包解，该用01背包解就用01背包解，当然多重背包可以用二进制优化分解成01背包。

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
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int dp[1010];
struct thing{
    int kind,v,w;
};
vector<thing> things;
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < n; i++){
        int v, w, s;
        cin >> v >> w >> s;
        if(s == -1) things.push_back({-1,v,w});
        else if(s == 0) things.push_back({0,v,w});
        else{
            for(int k = 1; k <= s; k*=2){
                s -= k;
                things.push_back({-1,v*k,w*k});
            }
            if(s > 0) things.push_back({-1,v*s,w*s});
        }
    }
    for(auto thing : things){
        if(thing.kind == -1){
            for(int j = m; j >= thing.v; j--){
                dp[j] = max(dp[j],dp[j-thing.v]+thing.w);
            }
        }else{
            for(int j = thing.v; j <= m; j++){
                dp[j] = max(dp[j],dp[j-thing.v]+thing.w);
            }
        }
    }
    cout << dp[m];
    return 0;
}