多重背包

朴素版本(O(n * v * s))

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 <algorithm>

using namespace std;
const int N = 110;

int v[N], w[N], s[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] >> s[i];

    for(int i = 1; i <= n; i ++){//枚举背包
        for(int j = 1; j <= m; j ++){//枚举体积
            for(int k = 0; k <= s[i]; k ++){
                if(j >=  k * v[i]){
                    f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
                }
            }
        }
    }

    cout << f[n][m] << endl;

    return 0;
}

优化版本: 二进制优化

二进制优化，它为什么正确，为什么合理

分析：

  • 如果直接遍历转化为01背包问题，是每次都拿一个来问，取了好还是不取好。那么根据数据范围，这样的时间复杂度是O(n3)也就是109109，这样是毫无疑问是会TLE的。

  • 所以需要用二进制进行分堆取，这里我看到一个很棒的解释，引用一下

    取这样一个例子:要求在一堆苹果选出n个苹果。我们传统的思维是一个一个地去选，选够n个苹果就停止。这样选择的次数就是n次

    二进制优化思维就是：现在给出一堆苹果和10个箱子，选出n个苹果。将这一堆苹果分别按照1,2,4,8,16,.....512分到10个箱子里，那么由于任何一个数字x∈[0,1023] (第11个箱子才能取到1024)都可以从这10个箱子里的苹果数量表示出来，但是这样选择的次数就是 ≤10次 。

    如果要拿1001次苹果，传统就是要拿1001次；二进制的思维，就是拿7个箱子就行（分别是装有512、256、128、64、32、8、1个苹果的这7个箱子）,这样一来，1001次操作就变成7次操作就行了。

    这样复杂度就降为O(n^2 * logS)

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
42
43
44
45
46
#include<iostream>
using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 体积<M

int main()
{
    cin >> n >> m;
    int cnt = 0; //分组的组别
    for(int i = 1;i <= n;i ++)
    {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1; // 组别里面的个数
        while(k<=s)
        {
            cnt ++ ; //组别先增加
            v[cnt] = a * k ; //整体体积
            w[cnt] = b * k; // 整体价值
            s -= k; // s要减小
            k *= 2; // 组别里的个数增加
        }
        //剩余的一组
        if(s>0)
        {
            cnt ++ ;
            v[cnt] = a*s; 
            w[cnt] = b*s;
        }
    }

    n = cnt ; //枚举次数正式由个数变成组别数

    //01背包一维优化
    for(int i = 1;i <= n ;i ++)
        for(int j = m ;j >= v[i];j --)
            f[j] = max(f[j],f[j-v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}

分组背包

duochong

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
42
#include <iostream>
#include <algorithm>
 
using namespace std;

const int N = 110;

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

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