动态规划

只有多练才能积累，之后就变练变总结，不要写云里雾里的东西了。

背包问题

背包问题（Knapsack problem）是一种组合优化的NP完全（NP-Complete，NPC）问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。一般来讲，背包问题有以下几种分类：

  • 01背包问题

  • 完全背包问题

  • 多重背包问题

01背包问题

动态规划重点的是状态转移方程:01背包，代表着物品只有两种可能性 - 放和不放

f[i][j]中的前i件物品放入容量为j的背包中。我们很容易可以看出，数组的第一个维度我们存储的是物品的不同种类，第二个维度存储的是我们的背包容量。

可以这样理解，f[i][j]就是i物品放入背包容量为j的状态

更新容量我们就使用：max(f[i-1][j-w[i]]+c[i],f[i-1][j])

当然放入物品的时候有两种情况，我们分别判断一下：
第一种，不放入我们的物品。f[i][j] = f[i-1][j]:这里很好理解，遍历到i-1这个物品，放入不下j就不变化 , 状态不更新把状态传下去。

第二种，放入我们的物品。这里就要考虑代价，也就是f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+c[i]) , 放入物品减去对应的体积吗，更新对应的值。记住每一个位置表示着一个状态。

1
2
3
4
5
6
7
8
9
//模版思想研究
//用二维数组来理解
 for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            if(j<w[i]) //先决条件：这个位置放不了i这个物品了
                f[i][j] = f[i-1][j];
      else
                f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+c[i]); 
   cout<<f[n][m];

用二维数组来理解十分容易，但是会浪费一些容量。我们不妨使用滚动数组来构造背包问题。思路如下：

  • 外层循环遍历每个物品i。

  • 内层循环遍历背包的容量j。

  • 如果当前物品的重量w[i]大于背包的容量j，表示无法将物品i放入背包中，因此f[j]的值不变，即f[j] = f[j]。这对应于提到的不放入我们的i情况。

否则，如果w[i]小于或等于背包容量j，表示可以考虑将物品i

放入背包中。在这种情况下，需要比较两种情况：

f[j]表示不放入物品i时的最大价值（对应于提到的f[j] = f[j]情况）。

f[j-w[i]] + c[i]表示放入物品i后的最大价值，其中f[j-w[i]]是在剩余容量j-w[i]下的最大价值，而c[i]是物品i的价值。你需要选择这两种情况中的较大值作为f[j]的新值，即f[j] = max(f[j], f[j-w[i]] + c[i])。

1
2
3
4
5
//用j逆序排序
 for(int i = 1;i<=n;i++)
        for(int j = m;j>=1;j--)
            if(j<w[i]) f[j] = f[j];
      else f[j] = max(f[j],f[j-w[i]]+c[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 <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;

int N, V; // N表示物品个数，V表示背包容量
int w[MAXN], v[MAXN]; // w[i]表示第i个物品的重量，v[i]表示第i个物品的价值
int dp[MAXN]; // dp[i]表示容量为i的背包所能装下的最大价值

int main() {
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> v[i];
    }

    memset(dp, 0, sizeof(dp)); // 初始化dp数组
    for (int i = 1; i <= N; i++) {
        for (int j = V; j >= w[i]; j--) { // 从后往前遍历，避免重复选择物品
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]); // 状态转移方程
        }
    }

    cout << dp[V] << endl; // 输出结果

    return 0;
}

完全背包问题*

完全背包问题，就是01背包的变形，每个物品可以无限次放入。f[i][j]依然和01背包问题相同的，i表示的是我们物品的种类，j表示的是我们背包的容量。放入物品的时候，我们需要选择放入这个物品我们的价值是否会增加

过程:

背包容量放不下我们当前这个物品 条件就是j<w[i] 所以说我们的容量还是不变f[i][j] = f[i-1][j]; (这也就解释了我们可以使用一维数组来维护我们的背包)，这里的i-1表示的是前一个物品，就是我们不会改变当前的背包状态

  • 当背包可以放入我们当前这个物品，条件也就是j>=w[i]我们有两种选择 - 放入和不放入。放入的话就是 f[i][j] = f[i][j-w[i]]+c[i]

  • c[i]是我们的价值(这里的i的意思就是我们物品是无穷的，每一个i表示的意思就是取出当前i这个物品的其中一个)

        不放入就是
   ` f[i][j] = f[i-1][j] `  j就不会变化

  • 我们最终的转移方程就是 上面两个合并的结果

       `f[i][j] = f[i-1][j] (j<w[i])`
   `f[i][j] = max(f[i-1][j],f[i][j-w[i]]+c[i])`

下面是代码模版：

1
2
3
4
5
6
7
for(int i = 1;i<=n;i++)
 for(int j = 1;j<=m;j++) //这里m是容量
 {
  if(j<w[i]) f[i][j] = f[i-1][j];
  else f[i][j] = max(f[i-1][j],f[i][j-w[i]]+c[i]); //c[i]是i物品的价值
 }
printf("%d",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
#include <iostream>
#include <vector>
using namespace std;

// 完全背包问题的动态规划解法
int knapsack(int W, vector<int>& wt, vector<int>& val) {
    int n = wt.size();
    vector<int> dp(W + 1, 0);

    for (int i = 1; i <= n; i++) {
        for (int j = wt[i-1]; j <= W; j++) {
            dp[j] = max(dp[j], dp[j - wt[i-1]] + val[i-1]);
        }
    }

    return dp[W];
}

// 测试
int main() {
    vector<int> wt = {2, 3, 4, 5};
    vector<int> val = {3, 4, 5, 6};
    int W = 8;
    cout << "最大价值为：" << knapsack(W, wt, val) << endl;
    return 0;
}

多重背包问题

在01背包的基础之上，让每一种物品都有对应的容量。只需要多加一个枚举数量的变量就行。

image-20230320145415756

需要注意的是，for循环枚举的是位置，而不是值。

1
2
3
4
5
6
7
8
9
10
11
//在01背包的基础上，让每一件物品都有他们的数量
 //1.v[i],w[i] 体积和价值
 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]);
 //2.v[i],w[i],s[i]; 体积 价值 数量 
        for(int i = 1;i<=n;i++)
            for(int j = m;j>=v[i];j--)
                for(int k = 0;k<=s[i]&&k*v[i]<=j;k++) 
                    //这里的k表示的是选择物品的数量 - s[i]表示的是当前位置的i物品的数量
                    f[j] = max(f[j],f[j-k*v[i]]+k*w[i]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//朴素做法
const int N = 1e5+10;
int v[N],w[N],s[N]; //体积 价值 数量
int f[N][N]; //这个是我们的状态转移数组

int main()
{
    cin>>n>>m;
    
    for( int i = 1;i<=n;i++) cin>>v[i]>>w[i]>>s[i]; //这里就是输入对应的价值，由i下标规定数据
    for(int i = 1;j<=n;j++)
        for(int j = 0;j<=m;j++)
            for(int k = 0;k<=s[i]&&k*v[i]<=j;k++)
                f[i][j] = max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k); //这里i-1是把这个i物品选择了（选够了就剔除） - 只要找到一个符合的k就行（我们不管怎么实现的就行）
    cout<<f[n][m]<<endl;
    return 0;
    
}

image-20230320145513754

image-20230320145617888

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int num = 1;//拆分计数
for(int i = 1;i<=n;i++){
    //v,w,s; 体积，价值，数量
    cin>>v>>w>>s;
    for(int j = 1;j<=s;j<<=1){ //<<=是左移位赋值运算符,等价*2
        vv[num] = j*v; //存体积
        ww[num++] = j*w; //存价值
        s-=j;
    }
    if(s){
        //体积和价值拆分 - 封装为新的数组
        vv[num] = s*v;
        ww[num++] = s*w;
    }
}

//01背包问题 - 基础
 for(i = 1;i<num;i++)
        for(j = m;j>=vv[i];j--)
            f[j] = max(f[j],f[j-vv[i]]+ww[i]);
cout<<f[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
34
35
36
37
38
#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005; // 物品的最大数量
const int MAXV = 100005; // 背包的最大容量
int n, V; // 物品的数量和背包的容量
int w[MAXN], v[MAXN], s[MAXN]; // 分别表示物品的重量、价值和数量
int dp[MAXV]; // dp[i]表示容量为i的情况下，可以获得的最大价值

// 二进制优化
void binary_optimization(int x, int y) {
    for (int j = V; j >= x; j--) {
        for (int k = 0; k <= s[y] && k * x <= j; k++) {
            dp[j] = max(dp[j], dp[j - k * x] + k * y);
        }
    }
}

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= s[i]; j *= 2) {
            binary_optimization(w[i] * j, v[i] * j); // 调用二进制优化函数
            s[i] -= j;
        }
        if (s[i] > 0) {
            binary_optimization(w[i] * s[i], v[i] * s[i]);
        }
    }

    cout << dp[V] << endl; // 输出答案
    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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//二进制优化
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[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 ++ ;
            //这里是二进制优化的核心 - 就是将s拆成2进制
            //核心是将物品拆分为2的幂次方个物品
            //每次都拿s拆开二进制的数量
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    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;
}

分组背包问题

在01背包的基础上，增加了物品序列号。只需要将价值生成一个组的序列号就行，然后照常枚举出我们需要的值。

1
2
3
4
5
6
7
8
9
//朴素做法
for(int i = 1;i<=n;i++)
    for(int j = 1;j<=V;j++)//体积
        for(int k = 0;k<=s[i];k++) { //决策
            if(j>=v[i][k])
                f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
                //不选取i  选取i
        }
cout<<f[n][V];
1
2
3
4
5
6
7
8
9
//分组朴素做法
for(int i = 1;i<=n;i++)
 for(int j = 1;j<=V;j++)
  for(int k = 0;k<=s[i];k++)
  {
   if(j>=v[i][k])
    f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
  }
cout<<f[n][V];

应该也可以用二进制优化策略

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 = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[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;
        //这里是将s数量分二进制
        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;
        }
    }

    n = cnt;

    //2.这里就是选择最大
    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;
}