【蓝桥杯专项】动态规划_背包问题合集(Java)

✨哈喽，进来的小伙伴们，你们好耶！✨

🛰️🛰️系列专栏:【蓝桥杯专项】

✈️✈️本篇内容:动态规划_背包问题合集！

🚀🚀码云仓库gitee：Java数据结构代码存放!

⛵⛵作者简介：一名双非本科大三在读的科班Java编程小白，道阻且长，你我同行！

注：每个题的标题就是原题链接

 一、完全背包问题

问题描述

有 N 种物品和一个容量是 V

的背包，每种物品都有无限件可用。

第 i种物品的体积是 vi，价值是 wi。

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

输入格式

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

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

输出格式

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

数据范围

0 0

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

思路分析：在上篇博客博主就已经介绍了0/1背包问题，那么完全背包问题跟0/1背包问题的区别就是它考虑前i个物品每个物品可以被多次选择。 那么，老规矩，我们根据状态规划可以得到：

(朴素解法)

1、曲线救国，去掉k个物品i

2、求max：f[i-1,j-k*v[i]]

3、在加回来k个物品i

由此得到我们的状态转移方程为：f[i-1,j-v[i] * k] + k*w[i]

代码实现：

import java.util.*;
public class Main{
       public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [] v = new int[1001];
        int [] w = new int[1001];
        int [][] f = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.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-v[i] * k]+ k * w[i]);
                }
            }
        }
        System.out.println(f[n][m]);
        sc.close();
    }
}

运行结果：

 我们可以发现运行时间非常的慢，那么什么原因呢？一方面是因为Java语言实现数据结构本身就比较慢，可以看到我们的代码是通过了3层循环来实现，最坏情况下时间复杂度是(n * v^2)，时间复杂度很高，那么是否可以优化该背包问题的代码呢？

优化一：

通过比较0/1背包问题，通过f[i,j] 和 f[i,j-v] 的递推公式我们可以发现，若要求得f[i,j-v]的最大值，只需要求出f[i,j]的最大值在加上一个w[i]即可，具体如下：

 代码实现：

import java.util.*;
public class Main{
       public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [] v = new int[1001];
        int [] w = new int[1001];
        int [][] f = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
 
        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] = Math.max(f[i][j],f[i][j-v[i]]+w[i]);
        }
    }
        
        System.out.println(f[n][m]);
        sc.close();
    }
}

运行结果：

我们发现快了整整2000ms，因为优化后的代码少了一层循环，还是很可观的。

优化二、转换为一维数组来实现

代码实现：

import java.util.*;
public class Main{
       public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [] v = new int[1001];
        int [] w = new int[1001];
        int [] f = new int[m+1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
 
        for (int i = 1; i <=n ; i++) {
            for (int j = v[i]; j <=m ; j++) {
                f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
        }
    }
    
        System.out.println(f[m]);
        sc.close();
    }
}

注意我们这里的j是从v[i]开始的，即从小到大，与0/1背包问题不同的是0/1背包问题是从大到小,

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

原因：简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。

二、多重背包问题

问题描述

有 N 种物品和一个容量是 V的背包。

第 i种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

输入格式

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

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

输出格式

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

数据范围

0 0

输入样例

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

输出样例：

10

 思路：我们可以模仿完全背包问题的朴素解法直接写出代码：

import java.util.*;
public class Main{
       public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [] v = new int[101];
        int [] w = new int[101];
        int [] s = new int[101];
        int [][] f = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
            s[i] = sc.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-v[i] * k]+ k * w[i]);
                }
            }
        }
        System.out.println(f[n][m]);
    }
}

运行结果：

 那么如果题目给的n,v,s的比较大的话，暴力解法接不能通过了，这就需要我们考虑如何来进行优化。

 二进制优化：

博主对于本题的二进制优化也是第一次接触到，通过查阅了不少资料并且反复观看了讲解视频后的个人总结心得：

1、在完全背包中,我们可以通过两个状态转移方程：

f[i,j]=max(f[i−1,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−2v]+2w,.....)
最后推导出->  f[i][j]=max(f[i−1][j],f[i][j−v]+w)。

2、在多重背包中，我们的推导过程为：

f[i,j] = max(f[i−1,j],f[i−1,j−v]+w,f[i−1,j−2v]+2w,.....f[i−1,j−Sv]+Sw,)
f[i,j−v]= max(f[i−1,j−v],f[i−1,j−2v]+w,.....f[i−1,j−Sv]+(S−1)w,f[i−1,j−(S+1)v]+Sw)

我们可以发现f[i,j−v]的最后一项比f[i,j]多出来一项，这就令人很是难受，对于完全背包问题我们直接对求的结果在加上个w[i]便可求出最大值，那么对于本题我们首先要了解一点：

怎么比完全背包方程比较就多出了一项?

其实，一般从实际含义出发来考虑即可，这里是在分析f[i,j−v]这个状态的表达式，首先这个状态的含义是 从前i个物品中选，且总体积不超过(j-v)的最大价值， 我们现在最多只能选s个物品，因此如果我们选s个第i个物品，那么体积上就要减去 s∗v,价值上就要加上s∗w，那更新到状态中去就是 f[i−1,j−v−s∗v]+s∗w，提取公因式v，也就是f[i−1,j−(S+1)v]+Sw。

什么是二进制优化？

简单来说就是比如系统给出一个数1023，那么按照常规惯例一个一个枚举我们是不是要枚举1023次才能得到这个结果，那么二进制优化是怎么做的呢？比如1023，那么我们可以通过2^0,2^1,2^2 ……2^k，这里的k应该是9，为什么是9呢，因为用2^0~2^9之间的数字拼凑可以任意用来表示1~1023之间的任何数字，这样就大大减少了我们的枚举数量，也就是一个时间复杂度从Si -> logSi的一个提高，这里我参照了网上的一个特别有意思的案列，可以根据这个案列来理解：

原地址：二进制优化思维

二进制优化思维就是：现在给出一堆苹果和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^3)
降到O(n^2*logS),从4∗10^9降到了2∗10^7。

代码实现：

import java.util.Scanner;
 
public class Main {
    /** 多重背包问题
     *
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [] v = new int[25000];
        int [] w = new int[25000];
        int [] f = new int[25000];
        int count = 0;//用来表示还剩几种物品
        int a,b,s,k = 1;
        //k就相当于每次多少个物品
        for (int i = 1; i <= n ; i++) {
            a = sc.nextInt();//体积
            b = sc.nextInt();//价值
            s = sc.nextInt();//数量
            while(k<=s){
                count++;
                v[count] = a*k;
                w[count] = b*k;
                s -= k;
                k *= 2;
            }
 
            if(s>0){//如果还有多余空间
                count++;
                v[count] = a*s;
                w[count] = b*s;
            }
        }
        n = count;//重置count
 
        for (int i = 1; i <= n ; i++) {//这里写一遍0/1背包一维实现便可
            for (int j = m; j >=v[i] ; j--) {
                f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
            }
        }
 
        System.out.println(f[m]);
    }
}

三、分组背包问题

问题描述

有 N 组物品和一个容量是 V的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j是组内编号。

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

输入格式

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

接下来有 N组数据：

• 每组数据第一行有一个整数 Si，
• 表示第 i个物品组的物品数量；
• 每组数据接下来有 Si行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j个物品的体积和价值；
• 输出格式

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

  数据范围

  0 0 0

• 输入样例

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

  输出样例：

  8
  

思路非常简单，首先读懂题目，然后根据题意，朴素解法就可。

代码实现：

import java.util.*;
class Main {
    
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int maxV = 105;
    int maxN = 105;
    int N, M, V;
    int[] dp = new int[maxV];
    int[] v = new int[maxN];
    int[] w = new int[maxN];
    
    N = sc.nextInt(); V = sc.nextInt();
    for (int i = 0; i < N; i++) {
        M = sc.nextInt();
        for (int j = 0; j < M; j++) {
            v[j] = sc.nextInt();
            w[j] = sc.nextInt();
        }
            for (int j = V; j >= 0; j--) {
                for (int k = 0; k < M; k++) {
                    if (j >= v[k]) dp[j] = Math.max(dp[j], dp[j - v[k]] + w[k]);
                }
            }
        }
        System.out.println(dp[V]);
        }
    }