跳到主要内容

动态规划-背包问题

01背包问题​

题目​

题目链接：https://www.acwing.com/problem/content/description/2/

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

第 ii 件物品的体积是 viv_i，价值是 wiw_i。

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

输入格式​

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

接下来有 NN 行，每行两个整数 vi,wiv_i, w_i，用空格隔开，分别表示第 ii 件物品的体积和价值。

输出格式​

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

数据范围​

0<N,V≤10000 \lt N, V \le 1000

0<vi,wi≤10000<v_i,w_i≤1000

输入样例​

4 5
1 2
2 4
3 4
4 5

输出样例：​

8

思路O(n2)O(n^2)​

  • dp[i][j]表示前i个物品，背包容量为j下的最大价值

    • 有N件物品，需要进行N次决策，每一次对第i件物品进行决策

  • 当背包容量不够时j<v[i]，前i个物品最大价值即为前i-1个物品的最大价值

    • 即dp[i][j]=dp[i-1][j]

  • 当背包容量够的时候，分两种情况，选与不选第i个物品,两种情况取Max

    • 选i:dp[i][j]=dp[i-1][j-v[i]]+w[i]
    • 不选i:dp[i][j]=dp[i-1][j]

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<int> v(n + 1), w(n + 1);
    vector<vector<int> > f(n + 1, vector<int>(m + 1));
    //所有从前i个物品中选，容量不超过j的最大价值
    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][j]= max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

思路-空间优化为O(n)O(n)​

维优化：

  • 将状态dp[i][j]变成一维dp[j]，只需要做一个等价变形
  • dp[j]的含义：N件物品，背包容量为j下的最大价值
    • 注意枚举背包容量的时候必须从最大容量m开始枚举
  • 为什么需要逆序枚举：
    • 二维情况下，dp[i][j]是由上一轮i-1的状态得来的，dp[i][j]与dp[i-1][j]互不影响
    • 一维情况下，如果还是用正序枚举，那么dp[较小体积]更新得到dp[较大体积]，则有可能本该用第i-1轮的状态，却是用的第i轮的状态

如果j是顺序循环，那么f[j-w[i]]会先于f[j]更新，也就是说，会用新值f[j-w[i]]去更新f[j]，所以出错

  • 状态转移方程：dp[j]=max(dp[j],dp[j-v[i]+w[i])
  • 我们的代码中决策到第 i件物品（循环到第i轮），f[j]就是前i轮已经决策的物品且背包容量 j 下的最大价值。

具体过程如下：

  当还未进入循环时:
  f[0] = 0;  f[1] = 0;  f[2] = 0;  f[3] = 0;  f[4] = 0;  
  f[5] = 0;  f[6] = 0;  f[7] = 0;  f[8] = 0;  f[9] = 0; f[10] = 0;
  当进入循环 i == 1 时：w[i] = 5; v[i] = 4;
  j = 10：f[10] = max(f[10], f[6] + 5); 即max(0, 5) = 5; 即f[10] = 5;
  j = 9 ：f[9] = max(f[9], f[5] + 5); 即max(0, 5) = 5; 即f[9] = 5;
  j = 8 ：f[8] = max(f[8], f[4] + 5); 即max(0, 5) = 5; 即f[8] = 5;
  j = 7 ：f[7] = max(f[7], f[3] + 5); 即max(0, 5) = 5; 即f[7] = 5;
  j = 6 ：f[6] = max(f[6], f[2] + 5); 即max(0, 5) = 5; 即f[6] = 5;
  j = 5 ：f[5] = max(f[5], f[1] + 5); 即max(0, 5) = 5; 即f[5] = 5;
  j = 4 ：f[6] = max(f[4], f[0] + 5); 即max(0, 5) = 5; 即f[4] = 5;
  当进入循环 i == 2 时：w[i] = 6; v[i] = 5; 
  j = 10：f[10] = max(f[10], f[5] + 6); 即max(5, 11) = 11; 即f[10] = 11;
  j = 9 ：f[9] = max(f[9], f[4] + 6); 即max(5, 11) = 5; 即f[9] = 11;
  j = 8 ：f[8] = max(f[8], f[3] + 6); 即max(5, 6) = 6; 即f[8] = 6;
  j = 7 ：f[7] = max(f[7], f[2] + 6); 即max(5, 6) = 6; 即f[7] = 6;
  j = 6 ：f[6] = max(f[6], f[1] + 6); 即max(5, 6) = 6; 即f[6] = 6;
  j = 5 ：f[5] = max(f[5], f[0] + 6); 即max(5, 6) = 6; 即f[5] = 6;
  当进入循环 i == 3 时: w[i] = 7; v[i] = 6; 
  j = 10：f[10] = max(f[10], f[4] + 7); 即max(11, 12) = 12; 即f[10] = 12;
  j = 9 ：f[9] = max(f[9], f[3] + 6); 即max(11, 6) = 11; 即f[9] = 11;
  j = 8 ：f[8] = max(f[8], f[2] + 6); 即max(6, 6) = 6; 即f[8] = 6;
  j = 7 ：f[7] = max(f[7], f[1] + 6); 即max(6, 6) = 6; 即f[7] = 6;
  j = 6 ：f[6] = max(f[6], f[0] + 6); 即max(6, 6) = 6; 即f[6] = 6;
数据来源：https://www.acwing.com/solution/content/30250/

代码​

#include <bits/stdc++.h>


using namespace std;

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<int> v(n + 1), w(n + 1);
    vector<int> f(m + 1);
    //所有从前i个物品中选，容量不超过j的最大价值
    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[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}

完全背包问题​

题目​

链接：https://www.acwing.com/problem/content/3/

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

第 ii 种物品的体积是 viv_i，价值是 wiw_i。

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

输入格式​

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

接下来有 NN 行，每行两个整数 vi,wiv_i, w_i，用空格隔开，分别表示第 ii 种物品的体积和价值。

输出格式​

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

数据范围​

0<N,V≤10000 \lt N, V \le 1000
0<vi,wi≤10000 \lt v_i, w_i \le 1000

输入样例​

4 5
1 2
2 4
3 4
4 5

输出样例：​

10

思路(朴素做法)​

f[i][j]表示将前i件物品放进容量为j的背包的最大价值

  • 如果当前背包容量j<w[i],不能放入，则f[i][j]=f[i-1][j]
  • 如果当前背包容量j>=w[i],可以放入：
    • 若第i件物品不放入,则f[i][j]=f[i-1][j]
    • 若第i件物品放入，则f[i][j]=f[i][j-w[i]]+c[i]

状态转移方程：

  • f[i][j]=f[i-1][j],(j<w[i])
  • f[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i]),(j>=w[i])

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<int> v(n + 1), w(n + 1);
    vector<vector<int> > f(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (j < v[i]) f[i][j] = f[i - 1][j];
                else f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
            }
        }
    cout << f[n][m] << endl;

    return 0;
}

优化(一维空间)​

可以将空间优化掉一维，优化之后从前往后枚举即可，区别于01背包：

  • f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包

  • f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<int> v(n + 1), w(n + 1);
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    vector<int> f(m + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= m; j++) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m];

    return 0;
}

多重背包问题​

题目​

https://www.acwing.com/problem/content/description/4/

有 NN 种物品和一个容量是 VV 的背包。

第 ii 种物品最多有 sis_i 件，每件体积是 viv_i，价值是 wiw_i。

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

输入格式​

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

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

输出格式​

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

数据范围​

见不同思路

输入样例​

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：​

10

思路（朴素O(n∗m∗∑si)O(n*m*\sum{s_i})）​

数据范围为：

0<N,V≤1000 \lt N, V \le 100 0<vi,wi,si≤1000 \lt v_i, w_i, s_i \le 100

dp[i][j]表示从前i个物品中选，总体积不超过j的最大价值

根据第i个物品选多少个进行划分，假设选k个，则dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]*k]+w[i]*k)

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<int> v(n + 1), w(n + 1), s(n + 1);
    vector<vector<int> > f(n + 1, vector<int>(m + 1));
    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 * v[i] <= j; k++) {
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
            }
        }
    }
    cout << f[n][m];
    return 0;
}

思路(二进制 O(n∗m∗∑logsi)O(n*m*\sum{log{s_i}}))​

  • 二进制优化，举例说明，假设有11个商品

    • 正常背包的思路下，我们要求出含这组商品的最优解，我们要枚举12次（枚举装0，1，2....12个）。
    • 现在用二进制优化，把这11个商品分别打包成含商品个数为1个，2个，4个，4个（分别对应0001,0010,0100,0100）的四个”新的商品 “,
    • 这样将问题转化为01背包问题，对于每个商品，我们都只枚举一次，那么我们只需要枚举四次 ，就可以找出这含组商品的最优解。 这样就大大减少了枚举次数。

二进制拆分思想：将第i种物品拆分为若干件物品，每件物品的体积和价值乘以一个拆分系数(1,21,22,...2k−1,si−2k+11,2^1,2^2,...2^{k-1},s_i-2^k+1)

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<int> a, b;
    for (int i = 1; i <= n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 1; j <= s; j <<= 1) { //二进制拆分
            a.push_back(j * v);
            b.push_back(j * w);
            s -= j;
        }
        if (s){ //还剩下物品
            a.push_back(s*v);
            b.push_back(s*w);
        }
    }
    //01背包
    vector<int> f(m+1);
    for(int i=0;i<a.size();i++){
        for(int j=m;j>=a[i];j--){
            f[j]= max(f[j],f[j-a[i]]+b[i]);
        }
    }
    cout<<f[m];
    return 0;
}

思路(单调队列O(n∗m)O(n*m))​

规律1:

f数组是按类进行更新的，可以把f[0...m]按体积v的余数拆分为v个类。

  • f[0],f[v],f[2v],...f[kv]
  • f[1],f[1+v],...f[1+kv];
  • f[j],f[j+v],...f[j+kv];

其中j是v的余数，0<=j<=v−10<=j<=v-1,例如

  • f[0],f[2],f[4],f[6],f[8]
  • f[1],f[3],f[5],f[7],f[9]

规律2:

f[j]是由前面不超过数量s的同类值传递推得到的，这就相当于从前面宽度为s的窗口中挑选最大值来更新当前的值，因此，我们可以使用单调队列来维护窗口的最大值，从而将更新f[j]的次数降低为1次，这时候需要顺序更新f值，需要增加一个备份数组。

改造后如下顺序循环

  int n, m;
  cin >> n >> m;
  vector<int> v(n + 1), w(n + 1), s(n + 1);
  vector<int> f(m + 1), g(m + 1);
  for (int i = 1; i <= n; i++) {
      std::memcpy(g, f, sizeof f);
      for (int j = 1; j <= m; j++) {
          for (int k = 1; k <= s[i] && v[i] * s[i] <= j; k++)
              f[j]= max(g[j],g[j-k*v[i]]+k*w[i]);
      }
  }

image-20230513135053594

image-20230513142730706

每次去使用队头更新当前的最大值，但是注意队头不一定就是整个队列中的最大值，队头+还可以放入物品的价值是整个队列中最大的

  • h表示队头，t表示队尾,变量j表示类j∈[0,v)j\in[0,v),k表示背包容量
  • 维护的窗口为[k-sv,k-v]
  • 当前还可以放入物品的个数为(k-q[h]/v)
  • 如果用g[k]比用g[q[t]]更新f[x]获得更大价值，可以有g[k]+(x-k)/v*w>=g[q[t]]+(x-q[t])/v*w,即g[k]>=g[q[t]]+(k-q[t])/v*w,那么就将队尾出队，表明g[k]比g[q[t]]更有价值

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 2e4 + 10;
int f[N], g[N], q[N];//q数组存下标


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m, v, w, s;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        std::memcpy(g, f, sizeof f);
        cin >> v >> w >> s;
        for (int j = 0; j < v; j++) {
            int h = 0, t = -1;//h为头，t为尾
            for (int k = j; k <= m; k += v) {
                //q[h]不在窗口[k-s*v,k-v]中，队头出队
                if (h <= t && q[h] < k - s * v) h++;
                //使用队头最大值来更新f (k-q[h])/v是还可以放进物品的个数
                if (h <= t) f[k] = max(g[k], g[q[h]] + (k - q[h]) / v * w);
                //当前值比队尾更有价值，队尾出队
                while (h <= t && g[k] >= g[q[t]] + (k - q[t]) / v * w) t--;
                //下标入队，便于队头出队
                q[++t] = k;
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

混合背包问题​

题目​

链接：https://www.acwing.com/problem/content/7/

有 NN 种物品和一个容量是 VV 的背包。

物品一共有三类：

  • 第一类物品只能用1次（01背包）；
  • 第二类物品可以用无限次（完全背包）；
  • 第三类物品最多只能用 sis_i 次（多重背包）；

每种体积是 viv_i，价值是 wiw_i。

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

输入格式​

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

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

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

输出格式​

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

数据范围​

0<N,V≤10000 \lt N, V \le 1000
0<vi,wi≤10000 \lt v_i, w_i \le 1000
−1≤si≤1000-1 \le s_i \le 1000

输入样例​

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例：​

8

思路​

参考上面的01背包问题，完全背包问题，多重背包问题

可以将多重背包问题用二进制优化的思路转换为01背包问题，这样就只需要做01背包和完全背包问题了，

  • f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包

  • f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题

优化为1维之后：f[j]=max(f[j],f[j-v]+w)

  • 01背包：从m−>vm->v枚举
  • 完全背包：从v−>mv->m枚举

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<int> f(m + 1);
    for (int i = 1; i <= n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        if (s == 0) {//完全背包问题
            for (int j = v; j <= m; j++)
                f[j] = max(f[j], f[j - v] + w);
        } else {//多重背包问题和01背包问题
            if (s == -1) s = 1;
            for (int j = 1; j <= s; j <<= 1) {
                for (int k = m; k >= j*v; k--) {
                    f[k]= max(f[k],f[k-j*v]+j*w);
                }
                s-=j;
            }
            if (s){
                for(int k=m;k>=s*v;k--){
                    f[k]= max(f[k],f[k-s*v]+s*w);
                }
            }
        }
    }
    cout<<f[m]<<endl;

    return 0;
}

二维费用的背包问题

题目​

链接：https://www.acwing.com/problem/content/8/

有 NN 件物品和一个容量是 VV 的背包，背包能承受的最大重量是 MM。

每件物品只能用一次。体积是 viv_i，重量是 mim_i，价值是 wiw_i。

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

输入格式​

第一行三个整数，N,V,MN,V, M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 NN 行，每行三个整数vi,mi,wiv_i, m_i, w_i，用空格隔开，分别表示第 ii 件物品的体积、重量和价值。

输出格式​

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

数据范围​

0<N≤10000 \lt N \le 1000
0<V,M≤1000 \lt V, M \le 100
0<vi,mi≤1000 \lt v_i, m_i \le 100
0<wi≤10000 \lt w_i \le 1000

输入样例​

4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

输出样例：​

8

思路​

动态规划：

  • 状态表示：f[i,j,k]所有从前i个物品中选，并且总体积不超过j，总重量不超过k的选法的最大价值
  • 状态计算：f[i,j,k]=max(f[i-1,j,k],f[i-1,j-v1[i],k-v2[i]]+w[i])

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 110;
int f[N][N];


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m, w;//个数，体积，容量
    cin >> n >> m >> w;
    for (int i = 1; i <= n; i++) {
        int a, b, c;//体积，重量，价值
        cin >> a >> b >> c;
        for(int j=m;j>=a;j--){
            for(int k=w;k>=b;k--){
                f[j][k]= max(f[j][k],f[j-a][k-b]+c);
            }
        }
    }
    cout<<f[m][w];


    return 0;
}

分组背包问题

题目​

链接：https://www.acwing.com/problem/content/9/

有 NN 组物品和一个容量是 VV 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vijv_{ij}，价值是 wijw_{ij}，其中 ii 是组号，jj 是组内编号。

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

输出最大价值。

输入格式​

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

接下来有 NN 组数据：

  • 每组数据第一行有一个整数 SiS_i ii个物品组的物品数量；
  • 每组数据接下来有 SiS_i 行，每行有两个整数 vij,wijv_{ij}, w_{ij}，用空格隔开，分别表示第 ii 个物品组的第 jj 个物品的体积和价值；

输出格式​

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

数据范围​

0<N,V≤1000 \lt N, V \le 100
0<Si≤1000 \lt S_i \le 100 0<vij,wij≤1000 \lt v_{ij}, w_{ij} \le 100

输入样例​

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例：​

8

思路(朴素O(n∗v∗∑si)O(n*v*\sum{s_i}))​

状态表示：f[i][j]表示前i组物品，能放入容量为j的背包的最大价值

循环物品组，循环背包容量，对于第i组物品，容量为j的背包，有s+1种选法，取最大值

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;

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

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++) {
            cin >> v[i][j] >> w[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;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][m]<<endl;

    return 0;
}

思路(空间优化1维)​

  • dp[j]表示总体积为j时的最大价值
  • 必须先枚举体积，再枚举每一个物品。因为如果先枚举物品，那么你下一个物品不管从哪里转移都已经被上一个更新，
  • 同时，体积必须倒着枚举，否则一个物品将会被重复选择。

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;

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

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 1; j <= s; j++) cin >> v[j] >> w[j];
        for (int j = m; j >= 1; j--) {
            for(int k=0;k<=s;k++){
                if (j>=v[k]){
                    f[j]= max(f[j],f[j-v[k]]+w[k]);
                }
            }
        }
    }
    cout<<f[m];

    return 0;
}

有依赖的背包问题

题目​

链接：https://www.acwing.com/problem/content/10/

有 NN 个物品和一个容量是 VV 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如下图所示：
QQ图片20181018170337.png

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 ii，体积是 viv_i，价值是 wiw_i，依赖的父节点编号是 pip_i。物品的下标范围是 1…N1 … N。

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

输出最大价值。

输入格式​

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

接下来有 NN 行数据，每行数据表示一个物品。
第 ii 行有三个整数 vi,wi,piv_i, w_i, p_i，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1p_i = -1，表示根节点。 数据保证所有物品构成一棵树。

输出格式​

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

数据范围​

1≤N,V≤1001 \le N, V \le 100
1≤vi,wi≤1001 \le v_i, w_i\le 100

父节点编号范围：

  • 内部结点：1≤pi≤N1 \le p_i \le N;
  • 根节点 pi=−1p_i = -1;

输入样例​

5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2

输出样例：​

11

思路​

考虑以u为根节点的子树的所有物品，这颗子树的物品都最大价值应该是节点u和背包容量j的函数

f[u][j]表示选择以u为子树的物品，在体积和不超过j时的最大价值

每个节点有i个节点s1,s2...sis_1,s_2...s_i可以选或者不选，可以将u的i个子节点看成i组物品,每组物品sis_i按体积拆分，有0,1,2,...j−v[i]0,1,2,...j-v[i]种决策

按单位体积拆分是因为sis_i的子孙有可能存在体积为1的物品，

拆分到j−v[u]j-v[u]是因为要留出v[u]v[u]到空间装入节点u的物品

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 110;
int n, m;
int v[N], w[N];
int h[N], e[N], ne[N], idx;
int f[N][N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {
    //f[u][i]表示以u为子树，体积不超过i的最大价值
    for (int i = v[u]; i <= m; i++) f[u][i] = w[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int to = e[i];
        dfs(to);
        for (int j = m; j >= v[u]; j--) {
            for (int k = 0; k <= j - v[u]; k++) {
                f[u][j] = max(f[u][j], f[u][j - k] + f[to][k]);
            }
        }
    }
}


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n >> m;
    memset(h, -1, sizeof h);
    int root;
    for (int i = 1; i <= n; i++) {
        int p;//每个节点的父节点
        cin >> v[i] >> w[i] >> p;
        if (p == -1) root = i;
        else add(p, i);
    }
    dfs(root);
    cout << f[root][m];
    return 0;
}

背包问题求方案数

题目​

链接：https://www.acwing.com/problem/content/11/

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

第 i$$i 件物品的体积是 viv_i，价值是 wiw_i。

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

输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+710^9 + 7 的结果。

输入格式​

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

接下来有 NN 行，每行两个整数 vi,wiv_i, w_i，用空格隔开，分别表示第 ii 件物品的体积和价值。

输出格式​

输出一个整数，表示 方案数 模 109+710^9 + 7 的结果。

数据范围​

0<N,V≤10000 \lt N, V \le 1000 0<vi,wi≤10000\lt v_i, w_i \le 1000

输入样例​

4 5
1 2
2 4
3 4
4 6

输出样例：​

2

思路​

f[i]表示背包容量为i时能装入物品的最大价值

c[i]表示背包容量为i时最优选法的方案数

容量从j-v增加到j，只是增加了一件物品，方案数没有改变c[j]=c[j-v]

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int n, m;

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n >> m;
    vector<int> f(m + 1), c(m + 1, 1);//不选也是一种方案
    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j--) {
            if (f[j - v] + w > f[j]) {//
                f[j] = f[j - v] + w;
                c[j] = c[j - v];//只是增加一个物品，方案数不变
            } else if (f[j - v] + w == f[j]) {//说明有新的选法
                c[j] = (c[j] + c[j - v]) % mod;
            }
        }
    }
    cout<<c[m]<<endl;


    return 0;
}

恰好装满01背包问题：

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int n, m;

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n >> m;
    vector<int> f(m + 1,-1000);
  	f[0]=0,c[0]=1;
    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j--) {
            if (f[j - v] + w > f[j]) {//
                f[j] = f[j - v] + w;
                c[j] = c[j - v];//只是增加一个物品，方案数不变
            } else if (f[j - v] + w == f[j]) {//说明有新的选法
                c[j] = (c[j] + c[j - v]) % mod;
            }	
        }
    }
    cout<<c[m]<<endl;


    return 0;
}

背包问题求具体方案

题目​

链接：https://www.acwing.com/problem/content/12/

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

第 i$$i 件物品的体积是 viv_i，价值是 wiw_i。

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

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N1 … N。

输入格式​

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

接下来有 NN 行，每行两个整数 vi,wiv_i, w_i，用空格隔开，分别表示第 ii 件物品的体积和价值。

输出格式​

输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 1…N1 … N。

数据范围​

0<N,V≤10000 \lt N, V \le 1000
0<vi,wi≤10000\lt v_i, w_i \le 1000

输入样例​

4 5
1 2
2 4
3 4
4 6

输出样例：​

1 4

思路​

状态表示：f[i][j]表示从第i个物品到最后一个物品装入容量为j的背包的最优解

与之前的区别就是这里是倒着的

选第i个：f[i][j]=f[i+1][j]

不选：f[i][j]=f[i+1][j-v[i]]+w[i]

计算完状态后：f[1][m]就是最大价值，从f[1][m]开始搜索

对于f[i][j]得到的方式，确定是否选择第i个物品：

  • f[i][j]=f[i+1][j],不选第i个物品
  • f[i][j]=f[i+1][j-v[i]]+w[i],选第i个物品
  • f[i][j]=f[i+1][j]=f[i+1][j-v[i]]+w[i],都可以得到最优解，为了字典序最小，必须选。

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<vector<int> > f(n + 2, vector<int>(m + 1));
    vector<int> v(n + 2), w(n + 2);
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i + 1][j];
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    }

    int j = m;
    for (int i = 1; i <= n; i++) {
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
            cout << i << " ";
            j -= v[i];
        }
    }


    return 0;
}
0%