动态规划

递归关系

  • 状态表示f[i,j]
    • 集合
    • 属性
  • 状态计算——集合划分

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
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];     //体积和价值
//int f[N][N];        //第一个N表示取第1~n个物品，第二个n表示从1开始到m的容量
 int f[N];          //采用滚动数组，滚动数组的本质还是减少空间复杂度

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )    cin >> v[i] >> w[i];      

    for (int i = 1; i <= n; i ++)           //从一个物品开始取
            for (int j = m; j >= v[i]; j --)        //从后向前更新，因为需要f[i - 1]层的数据
//       for (int j = 1; j <= m; j ++)       //逐渐增大背包容量至m            
            {
                f[j] = f[j];            //可以省略
 //             f[i][j] = f[i - 1][j];   
                f[j] = max(f[j], f[j - v[i]] + w[i]);                       
//             if (j >= v[i]) 
//                  f[i][j] = max(f[i][j], f[i -1][j - v[i]] + w[i]);
 
            }
        cout << f[m] << ' ';
        return 0;
}


4 5
1 2
2 4
3 4
4 5
// 物品是由小到大排列的
v[i] = 1 2 3 4
w[i] = 2 4 4 5
    1 2 3 4 5       j
0   0 0 0 0 0
1   2 2 2 2 2   
2   2 4 6 6 6 
3   2 4 6 6 8 
4   2 4 6 6 8


i

完全背包

  • 每个物品有无限个

  • 状态表示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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    cin >> n >> m;
    for (int i = 1; i <=  n; i ++ )  cin >> v[i] >> w[i];

    for (int i = 1;i <= n; i ++)
        for (int j = v[i]; j <= m; j ++ )          //正序更新,依赖于当前f[i]层的数据
 //              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]);        //与01背包思想差不多
 //                 f[j] = f[j - 1]                   
                    f[j] = max(f[j], f[j - v[i]] + w[i]);
      cout << f[m] << endl;
//    cout << f[n][m] << endl;
    return 0;
}



//f[i,j] = Max(f[i][j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,f[i-1,j-3v]+3w,…)

//f[i,j-v] = Max( f[i-1,j-v] ,f[i-1,j-2v]+w,f[i-1,j-3v]+2w,…)

完全背包与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
42
43
44
45
46
47
48
49

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25000;           // 1000 *log2 (200)

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

int f[N];

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;
            k *= 2;
        }
        if (s > 0)
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }			//转化为01背包问题

    n = cnt;
    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;
}

分组背包

  • 每组只能选一个