背包问题(背包九讲)

背包问题(背包九讲)背包九讲概述本文参考自bilibili上up主大雪菜的背包九讲专题:背包九讲专题1、背包九讲专题2以及AcWing上的相关讲解。背包问题代表了一类问题,即组合类的最优化问题,就是如果给我们一堆物品(元素),我们要按照某种限从中选出若干个物品(元素),求最大/最小值。本文将将对如下的九种背包问题给出分析过程以及实现代码(提供C++和Java代码,代码链接:github)/*1.01背包问题2.完全背包问题3.多重背包问题4.混合背包问题5.二维费用背包问题6.分

背包九讲

概述

本文参考自bilibili上up主大雪菜的背包九讲专题:背包九讲专题1背包九讲专题2 以及AcWing上的相关讲解。

  • 背包问题代表了一类问题,即组合类的最优化问题,就是如果给我们一堆物品(元素),我们要按照某种限从中选出若干个物品(元素),求最大/最小值。

  • 本文将将对如下的九种背包问题给出分析过程以及实现代码(提供C++和Java代码,代码链接:github),最后还给出了Leetcode上部分相关的背包问题以及解答。

    /*
    1. 01背包问题
    2. 完全背包问题
    3. 多重背包问题
    4. 混合背包问题
    5. 二维费用背包问题
    6. 分组背包问题
    7. 背包问题求方案数
    8. 求背包问题的方案
    9. 有依赖的背包问题
    */
    
  • 背包问题是一类典型的动态规划问题,一般对于动态规划问题,常规分析方式是给出状态定义状态转移,这里为了更加容易理解,采用yxc提出的闫式dp分析法

一. 01背包问题

问题描述

分析

在这里插入图片描述

代码

  • C++:
// Created by WXX on 2021/2/24 13:46
#include <iostream>

using namespace std;

const int N = 1010;  // 多开几个数据,防止数组下标越界

int n, m;  // 物品种类数,背包容积
int v[N], w[N];  // 体积,价值。注意:v[1]存储第一件物品,索引0未使用
int f[N][N];  // dp数组

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

    // 算法过程,因为f[0][0~m]初始就为0,因此初始化可以省略
    for (int i = 1; i <= n; i++) { 
     // 先循环物品
        for (int j = 0; j <= m; j++) { 
     // 再循环容量
            // 最后循环决策
            f[i][j] = f[i - 1][j];  // 不选第i件物品
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);  // 考虑选第i件物品
        }
    }
    cout << f[n][m] << endl;
    return 0;
}
  • Java
import java.util.Scanner;

// Created by WXX on 2021/2/24 14:15
public class Main { 
   

    public static final int N = 1010;  // 多开几个数据,防止数组下标越界

    static int n, m;  // 物品种类数,背包容积
    static int[] v = new int[N], w = new int[N];  // 体积,价值。注意:v[1]存储第一件物品,索引0未使用
    static int[][] f = new int[N][N];   // dp数组

    public static void main(String[] args) { 
   
        // 读入数据
        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); m = sn.nextInt();
        for (int i = 1; i <= n; i++) { 
   
            v[i] = sn.nextInt(); w[i] = sn.nextInt();
        }

        // 算法过程,因为f[0][0~m]初始就为0,因此初始化可以省略
        for (int i = 1; i <= n; i++) { 
     // 先循环物品
            for (int j = 0; j <= m; j++) { 
     // 再循环容量
                // 最后循环决策
                f[i][j] = f[i - 1][j];  // 不选第i件物品
                if (j >= v[i]) f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]);  // 考虑选第i件物品
            }
        }
        System.out.println(f[n][m]);
    }
}

代码优化(只用C++演示)

  • 考虑到在计算 f 的时候,当计算第 i 行时,只用到了第 i – 1 行的数据,因此可以用滚动数组优化
// Created by WXX on 2021/2/24 14:29
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[2][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 = 0; j <= m; j++) { 
   
            f[i & 1][j] = f[(i - 1) & 1][j];
            if (j >= v[i]) f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}
  • 其实这里还可以将 f 数组优化为一维数组,但是考虑到要用到上一行数据,因此第二层循环应该从大到小进行遍历,这样每次更新用到的就是未被更新的数据
// Created by WXX on 2021/2/24 14:36
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[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 = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

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

二. 完全背包问题

问题描述

分析

在这里插入图片描述

代码

  • C++:
// Created by WXX on 2021/2/24 14:52
#include <iostream>

using namespace std;

const int N = 1010;

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

// TLE
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 = 0; 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]);
    cout << f[n][m] << endl;
    return 0;
}
  • Java:
import java.util.Scanner;

// Created by WXX on 2021/2/24 14:58
public class Main { 
   

    public static final int N = 1010;

    static int n, m;
    static int[] v = new int[N], w = new int[N];
    static int[][] f = new int[N][N];

    public static void main(String[] args) { 
   

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); m = sn.nextInt();
        for (int i = 1; i <= n; i++) { 
   
            v[i] = sn.nextInt(); w[i] = sn.nextInt();
        }

        for (int i = 1; i <= n; i++)  // 先循环物品
            for (int j = 0; j <= m; j++)  // 再循环容量
                for (int k = 0; k * v[i] <= j; k++)  // 最后循环决策
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        System.out.println(f[n][m]);
    }
}

代码优化(只用C++演示)

  • 我们可以将 f ( i , j ) = f ( i − 1 , j − k ∗ v [ i ] ) + k ∗ w [ i ] f(i, j) = f(i-1, j-k*v[i]) + k*w[i] f(i,j)=f(i1,jkv[i])+kw[i] 展开,就可以发现如下规律:

    在这里插入图片描述

因此代码可以根据 f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i , j − v ) + w ) f(i, j) = max( f(i-1, j), f(i, j-v) + w) f(i,j)=max(f(i1,j),f(i,jv)+w) 进行优化:

// Created by WXX on 2021/2/24 15:21
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][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 = 0; j <= m; j++) { 
   
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}
  • 这里还可以将 f 数组优化为一维数组,因为不需要用到上一行数据,要用到本行之前计算出来的户籍,因此第二层循环应该从小到大进行遍历
// Created by WXX on 2021/2/24 15:21
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[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[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}

三. 多重背包问题

3.1 多重背包问题 I

问题描述

分析

在这里插入图片描述

代码

  • C++
// Created by WXX on 2021/2/24 16:07
#include <iostream>

using namespace std;

const int N = 110;

int n, m;
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];

    for (int i = 1; i <= n; i++)  // 先循环物品
        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 - k * v[i]] + k * w[i]);
    cout << f[n][m] << endl;
    return 0;
}
  • Java
import java.util.Scanner;

// Created by WXX on 2021/2/24 16:13
public class Main { 
   

    public static final int N = 110;

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

    public static void main(String[] args) { 
   

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); m = sn.nextInt();
        for (int i = 1; i <= n; i++) { 
   
            v[i] = sn.nextInt(); w[i] = sn.nextInt(); s[i] = sn.nextInt();
        }

        for (int i = 1; i <= n; i++)  // 先循环物品
            for (int j = 0; j <= m; j++)  // 再循环容量
                for (int k = 0; k <= s[i] && k * v[i] <= j; k++)  // 最后循环决策
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        System.out.println(f[n][m]);
    }
}

3.2 多重背包问题 II

问题描述

分析

  • 这一题不能使用类似于完全背包问题的方式进行优化,可以将 f ( i , j ) = f ( i − 1 , j − k ∗ v ) + k ∗ w , k = 0 , 1 , . . . , s f(i, j) = f(i-1, j-k*v) + k*w, k=0,1,…,s f(i,j)=f(i1,jkv)+kw,k=0,1,...,s 展开,如下:

    在这里插入图片描述

    我们发现 f [ i , j − v ] f[i, j-v] f[i,jv] 中比 f [ i , j ] f[i, j] f[i,j] 最后多了一项,不能直接得到这两者的关系,所以不能使用类似于完全背包问题的方式进行优化。

  • 本次的优化方式为二进制优化,将s件物品进行拆分,然后可以转化成01背包问题

    /*
    例如 s=10
    10可以拆分为0、1、2、4、3;
    前四个数可以凑出0~7之间的任何数据,加上3可以凑出3~10之间的任何数据,因此这5个数可以凑出0~10内的任何数据;
    相当于将10个物品打包成4个物品,打包后的物品的体积和价值分别为单个物品的1、2、4、3倍;
    这四个物品都是可选可不选,因此就转化成了01背包问题。
    
    例如 s=200
    200可以拆分为0、1、2、4、8、16、32、64、73;
    一共8个物品
    
    总结:对于s,可以划分为 log(s) 上取整个单一物品,然后用01背包问题的思路解决即可,时间复杂度:O(N*V*log(s))
    */
    

代码

  • C++
// Created by WXX on 2021/2/24 16:42
#include <iostream>
#include <vector>

using namespace std;

const int N = 2010;

int n, m;
int f[N];

struct Good { 
   
    int v, w;
};

int main() { 
   

    vector<Good> goods;
    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) { 
   
            s -= k;
            goods.push_back({ 
   k * v, k * w});
        }
        if (s > 0) goods.push_back({ 
   s * v, s * w});
    }

    for (auto good : goods)
        for (int j = m; j >= good.v; j--)
            f[j] = max(f[j], f[j - good.v] + good.w);
    cout << f[m] << endl;
    return 0;
}
  • Java
import java.util.ArrayList;
import java.util.Scanner;

// Created by WXX on 2021/2/24 16:50
public class Main { 
   

    public static final int N = 2010;

    static int n, m;
    static int[] f = new int[N];

    static class Good { 
   
        int v, w;
        public Good(int v, int w) { 
   
            this.v = v;
            this.w = w;
        }
    }

    public static void main(String[] args) { 
   

        ArrayList<Good> goods = new ArrayList<>();
        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); m = sn.nextInt();
        for (int i = 0; i < n; i++) { 
   
            int v = sn.nextInt(), w = sn.nextInt(), s = sn.nextInt();
            for (int k = 1; k <= s; k *= 2) { 
   
                s -= k;
                goods.add(new Good(k * v, k * w));
            }
            if (s > 0) goods.add(new Good(s * v, s * w));
        }

        for (Good good : goods)
            for (int j = m; j >= good.v; j--)
                f[j] = Math.max(f[j], f[j - good.v] + good.w);
        System.out.println(f[m]);
    }
}

3.2 多重背包问题 III

问题描述

分析

  • DP分析和 3.1 多重背包问题 I 完全一致,但是本题的数据量更大,需要进一步优化,这里采用滑动窗口求最值的方式优化

    在这里插入图片描述

    还有一个问题需要解决,就是窗口每次向右滑动一格,除了滑出窗口外的元素,其余的元素在下一次比较中都需要加上一个偏移量w,这个问题可以通过如下方式解决(参考网址):

    /*
    因为每次循环都只需要用到第i-1层的结果,所以在这里:
    g:第i-1层结果
    f:第i层结果
    
    如果一共有3个物品,即s=3的话:
    取r=1,那么f[3*v+1]的最大值为 f[3*v+1] = max(g[3*v+1], g[2*v+1]+w, g[v+1]+2w, g[1]+3w);
    
    
    所以我们可以得到下列算式:(其中r表示余数)
    f[r]=       g[r];
    f[r+v]= max(g[r] + w,  g[r+v]);
    f[r+2v]=max(g[r] + 2w, g[r+v] + w,  g[r+2v],);
    f[r+3v]=max(g[r] + 3w, g[r+v] + 2w, g[r+2v] + w, g[r+3v]);
    ……
    f[r+sv]=max(g[r] + sw,……, g[r+(s-1)v] + w, g[r+sv]);
    
    可以发现上面的等式上下存在偏移量w,所以可以减去kw再加上kw进行转换
    f[r]=       g[r];
    f[r+v]= max(g[r], g[r+v] - w) + w;
    f[r+2v]=max(g[r], g[r+v] - w, g[r+2v] - 2w) + 2w;
    f[r+3v]=max(g[r], g[r+v] - w, g[r+2v] - 2w, g[r+3v] - 3w) + 3w;
    ……
    f[r+sv]=max(g[r], ……, g[r+(s-1)v] - (s-1)w, g[r+sv] - sw) + sw;
    每次单调队列q (q中存储的是体积,如r,r+v,...) 用队尾数据和要插入的数据进行比较时,需要减去一个数
    这里比较的其实是上面max小括号中的数据
    队尾数据:g[a] - (a-r)/v * w,其中a是队尾体积q[tt] ==> g[q[tt]] - (q[tt]-r)/v * w
    即将滑入滑动窗口的数据:g[k] - (k-r)/v * w,其中k是当前考察的同余的体积,例如k=r+3v等
    
    另外还要注意,f中真实存储的数据为:g[q[hh]] + (q[hh]-r)/v * w,其中(q[hh]-r)/v * w为当前考察物品的收益
    */
    
  • 关于滑动窗口求最值,这是一个经典的问题,在LeetCode上有对应的问题:Leetcode 0239 滑动窗口最大值;在AcWing上也有对应的练习:AcWing 0154. 滑动窗口

  • 这里给出 Leetcode 0239 滑动窗口最大值 的C++解法(注意:这里的滑动窗口大小必须是k,不能小于k;多重背包中的滑动窗口为1,然后变为2,直到到达v后不再改变):

    // 考点:单调队列
    /** * 执行用时:240 ms, 在所有 C++ 提交中击败了97.90%的用户 * 内存消耗:114.1 MB, 在所有 C++ 提交中击败了88.81%的用户 */
    class Solution { 
         
    public:
        vector<int> maxSlidingWindow(vector<int> &nums, int k) { 
         
            int n = nums.size();
            int q[n];
            int hh = 0, tt = -1;
            vector<int> res;
            for (int i = 0; i < nums.size(); i++) { 
         
                if (hh <= tt && i - k + 1 > q[hh]) hh++;
                while (hh <= tt && nums[q[tt]] <= nums[i]) tt--;
                q[++tt] = i;
                if (i >= k - 1) res.push_back(nums[q[hh]]);
            }
            return res;
        }
    };
    

代码

// Created by WXX on 2021/2/24 18:43
#include <iostream>
#include <cstring>

using namespace std;

const int N = 20010;

int n, m;
int f[N], g[N], q[N];  // g存储上一行的值,f存储当前行的值,q是单调队列

int main() { 
   

    cin >> n >> m;
    for (int i = 0; i < n; i++) { 
     // 这里采取边读入物品,边处理;每个物品都要进行滑窗处理
        int v, w, s;
        cin >> v >> w >> s;
        memcpy(g, f, sizeof f);  // 将f中的数据拷贝到g中
        for (int r = 0; r < v; r++) { 
   
            int hh = 0, tt = -1;
            for (int k = r; k <= m; k += v) { 
   
                if (hh <= tt && q[hh] < k - s * v) hh++;  // 说明队头元素应该 滑出滑窗
                while (hh <= tt && g[q[tt]] - (q[tt] - r) / v * w <= g[k] - (k - r) / v * w) tt--;
                q[++tt] = k;  // 将当前考察体积存入滑窗
                if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}
  • Java
import java.util.Scanner;

// Created by WXX on 2021/2/24 19:37
public class Main { 
   

    public static final int N = 20010;
    static int n, m;
    static int[] f = new int[N], g = new int[N], q = new int[N];

    public static void main(String[] args) { 
   

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); m = sn.nextInt();
        for (int i = 0; i < n; i++) { 
     // 这里采取边读入物品,边处理;每个物品都要进行滑窗处理
            int v = sn.nextInt(), w = sn.nextInt(), s = sn.nextInt();
            System.arraycopy(f, 0, g, 0, N);  // 将f中的数据拷贝到g中
            for (int r = 0; r < v; r++) { 
   
                int hh = 0, tt = -1;
                for (int k = r; k <= m; k += v) { 
   
                    if (hh <= tt && q[hh] < k - s * v) hh++;  // 说明队头元素应该 滑出滑窗
                    while (hh <= tt && g[q[tt]] - (q[tt] - r) / v * w <= g[k] - (k - r) / v * w) tt--;
                    q[++tt] = k;  // 将当前考察体积存入滑窗
                    if (hh <= tt) f[k] = Math.max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
                }
            }
        }
        System.out.println(f[m]);
    }
}

四. 混合背包问题

问题描述

分析

  • 分不同情况下进行状态转移即可,如下图:

在这里插入图片描述

代码

  • C++
// Created by WXX on 2021/2/24 19:59
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main() { 
   

    cin >> n >> m;
    for (int i = 0; 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 { 
   
            if (s == -1) s = 1;  // 全部转为多重背包,然后使用二进制优化
            for (int k = 1; k <= s; k *= 2) { 
   
                for (int j = m; j >= k * v; j--)
                    f[j] = max(f[j], f[j - k * v] + k * w);
                s -= k;
            }
            if (s) { 
   
                for (int j = m; j >= s * v; j--)
                    f[j] = max(f[j], f[j - s * v] + s * w);
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}
  • Java
import java.util.Scanner;

// Created by WXX on 2021/2/24 20:06
public class Main { 
   

    public static final int N = 1010;

    static int n, m;
    static int[] f = new int[N];

    public static void main(String[] args) { 
   

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); m = sn.nextInt();
        for (int i = 0; i < n; i++) { 
   
            int v = sn.nextInt(), w = sn.nextInt(), s = sn.nextInt();
            if (s == 0) { 
     // 完全背包
                for (int j = v; j <= m; j++) f[j] = Math.max(f[j], f[j - v] + w);
            } else { 
   
                if (s == -1) s = 1;  // 全部转为多重背包,然后使用二进制优化
                for (int k = 1; k <= s; k *= 2) { 
   
                    for (int j = m; j >= k * v; j--)
                        f[j] = Math.max(f[j], f[j - k * v] + k * w);
                    s -= k;
                }
                if (s != 0) { 
   
                    for (int j = m; j >= s * v; j--)
                        f[j] = Math.max(f[j], f[j - s * v] + s * w);
                }
            }
        }
        System.out.println(f[m]);
    }
}

五. 二维费用背包问题

问题描述

分析

  • 需要说明一点,二维费用背包为可以和 01背包、完全背包、多重背包、分组背包 这四种类型背包中的任何一种组合起来。
  • 当前题目是和 01背包 绑定起来的题目

在这里插入图片描述

代码

  • C++
// Created by WXX on 2021/2/24 20:25
#include <iostream>

using namespace std;

const int N = 110;

int n, V, M;
int f[N][N];  // 第一维代表体积,第二维代表重量

int main() { 
   

    cin >> n >> V >> M;
    for (int i = 0; i < n; i++) { 
   
        int v, m, w;
        cin >> v >> m >> w;
        for (int j = V; j >= v; j--)
            for (int k = M; k >= m; k--)
                f[j][k] = max(f[j][k], f[j - v][k - m] + w);
    }
    cout << f[V][M] << endl;
    return 0;
}
  • Java
import java.util.Scanner;

// Created by WXX on 2021/2/24 20:34
public class Main { 
   

    public static final int N = 110;

    static int n, V, M;
    static int[][] f = new int[N][N];  // 第一维代表体积,第二维代表重量

    public static void main(String[] args) { 
   

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); V = sn.nextInt(); M = sn.nextInt();
        for (int i = 0; i < n; i++) { 
   
            int v = sn.nextInt(), m = sn.nextInt(), w = sn.nextInt();
            for (int j = V; j >= v; j--)
                for (int k = M; k >= m; k--)
                    f[j][k] = Math.max(f[j][k], f[j - v][k - m] + w);
        }
        System.out.println(f[V][M]);
    }
}

六. 分组背包问题

问题描述

分析

在这里插入图片描述

代码

  • C++
// Created by WXX on 2021/2/24 20:52
#include <iostream>

using namespace std;

const int N = 110;

int n, m;
// s[i]: 代表第i组物品的数量;v[i][k],w[i][k]: 第i组中第k个物品的体积和价值
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 (j >= v[i][k])
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m] << endl;
    return 0;
}
  • Java
import java.util.Scanner;

// Created by WXX on 2021/2/24 21:01
public class Main { 
   

    public static final int N = 110;

    static int n, m;
    // s[i]: 代表第i组物品的数量;v[i][k],w[i][k]: 第i组中第k个物品的体积和价值
    static int[] s = new int[N];
    static int[][] v = new int[N][N], w = new int[N][N];
    static int[] f = new int[N];

    public static void main(String[] args) { 
   

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); m = sn.nextInt();
        for (int i = 1; i <= n; i++) { 
   
            s[i] = sn.nextInt();
            for (int j = 0; j < s[i]; j++) { 
   
                v[i][j] = sn.nextInt(); w[i][j] = sn.nextInt();
            }
        }

        for (int i = 1; i <= n; i++)  // 先循环物品
            for (int j = m; j >= 0; j--)  // 再循环容量。因为某件物品要么选要么不选,所以递减遍历
                for (int k = 0; k < s[i]; k++)  // 最后循环决策
                    if (j >= v[i][k])
                        f[j] = Math.max(f[j], f[j - v[i][k]] + w[i][k]);
        System.out.println(f[m]);
    }
}

注意点

  • 其实 多重背包问题分组背包问题 的一个特例。

    对于多重背包问题:对于某个物品来说,如果出现 s 次,则可以选择0次,(1次…s次),我们将(1次…s次)这些情况打包起来形成一组,看成不同的物品(s个),我们最多从中选1个,因此有 s+1 种可能的情况。

七. 背包问题求方案数

问题描述

分析

  • 需要说明一点,和二维费用背包一样。背包问题求方案数可以和 01背包、完全背包、多重背包、分组背包 这四种类型背包中的任何一种组合起来。

  • 本题的本质是求最短路径的条数。其实动态规划的本质是图论问题

  • 我们可以根据背包问题的状态转移方程来分析方案数,这里状态转移方程是: f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i − 1 , j − v i ) + w i ) f(i,j)=max(f(i-1,j), f(i-1,j-vi)+wi) f(i,j)=max(f(i1,j),f(i1,jvi)+wi)。为了计算方案数,这里的 f ( i , j ) f(i,j) f(i,j) 定义需要做一下改变: f ( i , j ) f(i,j) f(i,j) 代表只从前 i 个物品中选,体积恰好是 j 的最大价值

  • 为了实现 f ( i , j ) f(i,j) f(i,j) 所定义的含义,我们需要在初始化是将 f(0, k),即第一行初始化为负无穷,且只有 f(0, 0) = 0。这样的话,负无穷所更新的状态仍然是负无穷,只有被 f(0, 0)更新的状态是有效的状态,因此体积恰好是 j。

  • 为了记录方案数,我们还需要另外开辟一个数组 g ( i , j ) g(i,j) g(i,j) ,代表的含义是: f ( i , j ) f(i,j) f(i,j) 取最大值时的方案数。 g ( i , j ) g(i,j) g(i,j) 的求解存在三种情况:

    (1)如果 f ( i − 1 , j ) f(i – 1,j) f(i1,j) > f ( i − 1 , j − v ) + w f(i – 1,j-v) + w f(i1,jv)+w ,则 g ( i , j ) g(i,j) g(i,j) = g ( i − 1 , j ) g(i – 1,j) g(i1,j)

    (2)如果 f ( i − 1 , j ) f(i – 1,j) f(i1,j) < f ( i − 1 , j − v ) + w f(i – 1,j-v) + w f(i1,jv)+w ,则 g ( i , j ) g(i,j) g(i,j) = g ( i − 1 , j − v ) g(i – 1,j-v) g(i1,jv)

    (3)如果 f ( i − 1 , j ) f(i – 1,j) f(i1,j) = f ( i − 1 , j − v ) + w f(i – 1,j-v) + w f(i1,jv)+w ,则 g ( i , j ) g(i,j) g(i,j) = g ( i − 1 , j ) g(i – 1,j) g(i1,j) + g ( i − 1 , j − v ) g(i – 1,j-v) g(i1,jv)

  • 因为本题对应的是 01背包问题,所以上面的二维数组都可以被优化为一维数组,只要在遍历体积的时候从大到小进行遍历即可。

代码

  • C++
// Created by WXX on 2021/2/24 21:56
#include <iostream>
#include <cstring>

using namespace std;

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

int n, m;
// f[i]: 表示体积恰好为j时的最大价值;g[i]: f[i]取最大值时的方案数
int f[N], g[N];

int main() { 
   

    cin >> n >> m;

    memset(f, -0x3f, sizeof f);
    f[0] = 0;
    g[0] = 1;  // 什么都不选也是一种方案

    for (int i = 0; i < n; i++) { 
   
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j--) { 
   
            int maxv = max(f[j], f[j - v] + w);
            int cnt = 0;
            if (maxv == f[j]) cnt += g[j];
            if (maxv == f[j - v] + w) cnt += g[j - v];
            g[j] = cnt % mod;
            f[j] = maxv;
        }
    }

    int res = 0;  // 最大价值,因为取到最大价值消耗的体积不一定恰好等于背包容量
    for (int i = 0; i <= m; i++) res = max(res, f[i]);

    int cnt = 0;  // 取到最大价值的方案数
    for (int i = 0; i <= m; i++)
        if (res == f[i])
            cnt = (cnt + g[i]) % mod;
    cout << cnt << endl;
    return 0;
}
  • Java
import java.util.Arrays;
import java.util.Scanner;

// Created by WXX on 2021/2/24 22:08
public class Main { 
   

    public static final int N = 1010, mod = (int)(1e9 + 7);

    static int n, m;
    // f[i]: 表示体积恰好为j时的最大价值;g[i]: f[i]取最大值时的方案数
    static int[] f = new int[N], g = new int[N];

    public static void main(String[] args) { 
   

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); m = sn.nextInt();

        Arrays.fill(f, Integer.MIN_VALUE);
        f[0] = 0;
        g[0] = 1;  // 什么都不选也是一种方案

        for (int i = 0; i < n; i++) { 
   
            int v = sn.nextInt(), w = sn.nextInt();
            for (int j = m; j >= v; j--) { 
   
                int maxv = Math.max(f[j], f[j - v] + w);
                int cnt = 0;
                if (maxv == f[j]) cnt += g[j];
                if (maxv == f[j - v] + w) cnt += g[j - v];
                g[j] = cnt % mod;
                f[j] = maxv;
            }
        }

        int res = 0;  // 最大价值,因为取到最大价值消耗的体积不一定恰好等于背包容量
        for (int i = 0; i <= m; i++) res = Math.max(res, f[i]);

        int cnt = 0;  // 取到最大价值的方案数
        for (int i = 0; i <= m; i++)
            if (res == f[i])
                cnt = (cnt + g[i]) % mod;
        System.out.println(cnt);
    }
}

八. 求背包问题的方案

问题描述

分析

  • 需要说明一点,和二维费用背包以及背包问题求方案数一样。求背包问题的方案可以和 01背包、完全背包、多重背包、分组背包 这四种类型背包中的任何一种组合起来。

  • 我们可以根据背包问题的状态转移方程来求背包的方案,这里状态转移方程是: f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i − 1 , j − v i ) + w i ) f(i,j)=max(f(i-1,j), f(i-1,j-vi)+wi) f(i,j)=max(f(i1,j),f(i1,jvi)+wi)。这里存在三种情况

    (1) f ( i , j ) f(i,j) f(i,j) == f ( i − 1 , j ) f(i-1,j) f(i1,j) f ( i , j ) f(i,j) f(i,j) > f ( i − 1 , j − v i ) + w i f(i-1,j-vi)+wi f(i1,jvi)+wi ,则最大价值的方案中必定不包含物品 i ;

    (2) f ( i , j ) f(i,j) f(i,j) > f ( i − 1 , j ) f(i-1,j) f(i1,j) f ( i , j ) f(i,j) f(i,j) == f ( i − 1 , j − v i ) + w i f(i-1,j-vi)+wi f(i1,jvi)+wi ,则最大价值的方案中必定包含物品 i ;

    (3) f ( i , j ) f(i,j) f(i,j) == f ( i − 1 , j ) f(i-1,j) f(i1,j) f ( i , j ) f(i,j) f(i,j) == f ( i − 1 , j − v i ) + w i f(i-1,j-vi)+wi f(i1,jvi)+wi ,则最大价值的方案中可包含也可不包含物品 i ;

  • 另外,本题还要求输出 字典序最小的方案,因此我们应该反过来遍历物品(从物品n开始遍历到物品1),求出数组 f 后,之后就可以从物品1开始考察,能选则选,然后考虑物品2,…,这样得到的结果字典序最小。如果还是从物品1开始遍历,则之后只能从物品n开始考察,无法保证字典序最小。

  • 注意:我们此时不能将二维数组压缩为一维数组,这是因为数组 f 中间的状态还需要被使用

  • 除了上面这种解决方案外,还可以通过创建一个bool数组记录某个物品是否应该被选择。

代码

  • C++
// Created by WXX on 2021/2/24 22:27
#include <iostream>

using namespace std;

const int N = 1010;

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

int main() { 
   

    cin >> n >> m;
    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 << ' ';  // 如果能选物品i的话一定要选,这样可保证字典序最小
            j -= v[i];
        }
    return 0;
}
  • Java
import java.util.Scanner;

// Created by WXX on 2021/2/24 22:33
public class Main { 
   

    public static final int N = 1010;

    static int n, m;
    static int[] v = new int[N], w = new int[N];
    static int[][] f = new int[N][N];

    public static void main(String[] args) { 
   

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); m = sn.nextInt();
        for (int i = 1; i <= n; i++) { 
   
            v[i] = sn.nextInt(); w[i] = sn.nextInt();
        }

        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] = Math.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]) { 
   
                System.out.print(i + " ");;  // 如果能选物品i的话一定要选,这样可保证字典序最小
                j -= v[i];
            }
    }
}

九. 有依赖的背包问题

问题描述

分析

  • 这一题是一道 树形DP 的问题
  • 这是一棵树,我们采取的存储方式邻接表,实现方式是数组模拟链表,这部分内容可以参照AcWing的算法基础课:网址

在这里插入图片描述

代码

  • C++
// Created by WXX on 2021/2/24 23:08
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N];
int h[N], e[N], ne[N], idx = 0;  // 邻接矩阵
int f[N][N];

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

void dfs(int u) { 
   

    for (int i = h[u]; ~i; i = ne[i]) { 
     // 遍历u的子节点,相当于循环物品组
        int son = e[i];
        dfs(son);  // 求解完成子节点后才能求解当前节点

        // 分组背包
        for (int j = m - v[u]; j >= 0; j--)  // 循环体积
            for (int k = 0; k <= j; k++)  // 循环决策
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    }

    // 将物品u加进去
    for (int i = m; i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + w[u];
    for (int i = 0; i < v[u]; i++) f[u][i] = 0;  // 不能放入物品u,则整棵子树都不能放入
}

int main() { 
   

    cin >> n >> m;
    memset(h, -1, sizeof h);
    int root = 1;  // 根节点并不一定是1号点
    for (int i = 1; i <= n; i++) { 
   
        int p;
        cin >> v[i] >> w[i] >> p;
        if (p == -1) root = i;
        else add(p, i);  // 添加一条由p指向i的边
    }
    dfs(root);
    cout << f[root][m] << endl;
    return 0;
}
  • Java
import java.util.Arrays;
import java.util.Scanner;

// Created by WXX on 2021/2/24 23:24
public class Main { 
   

    public static final int N = 110;

    static int n, m;
    static int[] v = new int[N], w = new int[N];
    // 邻接矩阵
    static int[] h = new int[N], e = new int[N], ne = new int[N];
    static int idx = 0;

    static int[][] f = new int[N][N];

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

    private static void dfs(int u) { 
   

        for (int i = h[u]; i != -1; i = ne[i]) { 
     // 遍历u的子节点,相当于循环物品组
            int son = e[i];
            dfs(son);  // 求解完成子节点后才能求解当前节点

            // 分组背包
            for (int j = m - v[u]; j >= 0; j--)  // 循环体积
                for (int k = 0; k <= j; k++)  // 循环决策
                    f[u][j] = Math.max(f[u][j], f[u][j - k] + f[son][k]);
        }

        // 将物品u加进去
        for (int i = m; i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + w[u];
        for (int i = 0; i < v[u]; i++) f[u][i] = 0;  // 不能放入物品u,则整棵子树都不能放入
    }

    public static void main(String[] args) { 
   

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); m = sn.nextInt();
        Arrays.fill(h, -1);
        int root = 1;  // 根节点并不一定是1号点
        for (int i = 1; i <= n; i++) { 
   
            v[i] = sn.nextInt(); w[i] = sn.nextInt();
            int p = sn.nextInt();
            if (p == -1) root = i;
            else add(p, i);  // 添加一条由p指向i的边
        }
        dfs(root);
        System.out.println(f[root][m]);
    }
}

LeetCode上一些背包问题

Leetcode 0279 完全平方数

问题描述

分析

  • 完全背包问题,把n当做背包容量,每个完全平方数当做物品,其对应的数值数值当做体积,每个数的价值都为1,则问题变成在恰好装满背包的情况下,总价值最少是多少。完全背包问题的时间复杂度为O(体积*物品个数),所以该题的时间复杂度为 O ( n ∗ n ) O(n* \sqrt n) O(nn
    )

在这里插入图片描述

代码

  • C++
/** * 执行用时:204 ms, 在所有 C++ 提交中击败了69.60%的用户 * 内存消耗:8.7 MB, 在所有 C++ 提交中击败了83.16%的用户 */
class Solution { 
   
public:
    int numSquares(int n) { 
   

        vector<int> f(n + 1, 1e9);  // f[i] 代表 i 最少可以由几个完全平方数表示
        f[0] = 0;
        for (int i = 1; i * i <= n; i++)  // 先循环物品 i*i
            for (int j = i * i; j <= n; j++)  // 再循环体积:体积从i*i开始
                f[j] = min(f[j], f[j - i * i] + 1);
        return f[n];
    }
};
  • Java
/** * 执行用时:30 ms, 在所有 Java 提交中击败了86.04%的用户 * 内存消耗:37.8 MB, 在所有 Java 提交中击败了34.09%的用户 */
public class Solution { 
   
    public int numSquares(int n) { 
   
        
        int[] f = new int[n + 1];
        Arrays.fill(f, Integer.MAX_VALUE);
        f[0] = 0;
        for (int i = 1; i * i <= n; i++)  // 先循环物品 i*i
            for (int j = i * i; j <= n; j++)  // 再循环体积:体积从i*i开始
                f[j] = Math.min(f[j], f[j - i * i] + 1);
        return f[n];
    }
}

Leetcode 0322 零钱兑换

问题描述

分析

  • 完全背包问题
  • amout为容量;物品体积为coins[i],价值为1
  • 和上一题十分类似,这里就不详细分析了

代码

  • C++
/** * 执行用时:64 ms, 在所有 C++ 提交中击败了89.56%的用户 * 内存消耗:13.7 MB, 在所有 C++ 提交中击败了66.94%的用户 */
class Solution { 
   
public:
    int coinChange(vector<int> &coins, int m) { 
   

        vector<int> f(m + 1, 1e8);
        f[0] = 0;
        for (auto v : coins)
            for (int j = v; j <= m; j++)
                f[j] = min(f[j], f[j - v] + 1);
        if (f[m] == 1e8) return -1;
        return f[m];
    }
};
  • Java
/** * 执行用时:12 ms, 在所有 Java 提交中击败了94.69%的用户 * 内存消耗:38.1 MB, 在所有 Java 提交中击败了22.43%的用户 */
public class Solution { 
   
    public int coinChange(int[] coins, int m) { 
   

        int[] dp = new int[m + 1];
        Arrays.fill(dp, m + 1);
        dp[0] = 0;
        for (int v : coins)
            for (int j = v; j <= m; j++)
                dp[j] = Math.min(dp[j], dp[j - v] + 1);

        return dp[m] == m + 1 ? -1 : dp[m];
    }
}

今天的文章背包问题(背包九讲)分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/24179.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注