DP3、

背包问题，从01背包->完全背包

01背包问题

该问题节选自 https://www.acwing.com/problem/content/2/

01背包-1

  • 题目很好理解，就是我们要选择一个最优方案，使得总价值最大，并且总体积不能超过背包容量.
  • 01背包问题的本质就是背包只有选或者不选两种可能.
  • 想象一下，如果我们使用暴力法，即枚举所有的可能， 一共是2^N的指数级别的时间复杂度，然后选择一个最优的方案.
  • 背包问题还有一个著名的标签，那就是动态规划了，接下来我们用动态规划的方式去思考！

01背包问题未优化版

  • 首先我们需要定义dp的状态，题目要求N件物品，容量为V的背包的最大价值.
  • 我们定义dp(i,j)为i件物品，容量为j的背包的总价值。那么很明显，我们最后所求得就是 dp(N,V).
  • 现在关键的问题是我们如何分解子问题，然后得到一个转移方程.
  • 首先我们考虑边界dp(0,0)表示取0个物品的总价值，那么很明显 dp(0,0)=0.
  • 接下来该如何考虑分解子问题呢？我们现在开始分析
    • 我们将总背包分为前i-1个背包和最后一个背包.
    • 并且最后一个背包有两种情况，选or不选.
    • 如果我们不选最后一个背包，那么很简单，此时dp(i,j)=dp(i-1,j).
    • 如果我们选了最后一个背包.此时最后一个背包的价值w[i]是一个固定值.我们为了使总价值最大，我们只需要让前i-1个物体的总价值达到最大.此时一共有前i-1个物体，并且对应的体积为j-v[i].那么很容易的，我们可以推出这个转移方程.
    • 此时dp(i,j)=max{dp(i-1,j),dp(i-1,j-v[i])+w[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
29
30
31
32
33
34
35
36
37
import java.util.Scanner;

public class Main{
    public static void main(String[] args) throws Exception {
      
        Scanner input = new Scanner(System.in);
    
        int N = input.nextInt();
        
        int V = input.nextInt();
       
        int[] v = new int[N + 1] ;
      
        int[] w = new int[N + 1] ;

        for (int i=1 ; i <= N ; i++){
          
            v[i] = input.nextInt();
            w[i] = input.nextInt();
        }
      

        
        int[][] dp = new int[N+1][V+1];
        dp[0][0] = 0;
        for(int i = 1; i <= N; i++){
            for(int j = 0; j <= V; j++){
                if(j >= v[i]){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[N][V]);
    }
}

我们利用一个二维数组对此问题进行了分析，并且实现，但是实际上，我们只需要用1维数组就可以实现该过程.

01背包问题优化

首先明确一点，dp问题所有的优化，我们只是在原代码的基础上进行等价变形，并且我们只能够优化空间复杂度.

我们尝试将上述问题转换为1维数组.

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
import java.util.Scanner;

public class Main{
    public static void main(String[] args) throws Exception {
      
        Scanner input = new Scanner(System.in);
    
        int N = input.nextInt();
        
        int V = input.nextInt();
       
        int[] v = new int[N + 1] ;
      
        int[] w = new int[N + 1] ;

        for (int i=1 ; i <= N ; i++){
          
            v[i] = input.nextInt();
            w[i] = input.nextInt();
        }
      

        
      //我们在原代码的基础上，只保留了dp(j)，所有关于背包个数，我们全部删除
        int[]dp = new int[V+1];
        dp[0] = 0;
        for(int i = 1; i <= N; i++){
            for(int j = 0; j <= V; j++){
                if(j >= v[i]){
                  //dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
                    dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
                  //dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i])
                }else{
                  //dp[i][j]=dp[i-1][j]
                    dp[j] = dp[j];
                }
            }
        }
        System.out.println(dp[N][V]);
    }
}

我们将之前的代码通过注释添加在了修改后的代码边上，方便我们做比较，此时我们首先可以看到下面这个等式.

  • 即此时dp(i,j)=dp(i-1,j) 与dp(j)=dp(j)是否等价？

  • 首先我们可以知道，我们应该是先算出dp(i-1,j)，然后将dp(i,j)进行更新.即此时两者是等价的.

  • 我们再来考虑第一个等式.该等式的实质就是比较dp[j], dp[j-v[i]] + w[i],两者的大小，然后更新dp[j].

  • 此时到底是为dp(i,j-v[i])还是为dp(i-1,j-v[i])，取决于我们这个它是在第i-1层还是第i层计算的， 明显我们是从小到大遍历j，且此时j-v[i]<j，即我们在算f(j)时，应该先算出f(j-v[i])，即此时我们是第i层的f(j-v[i]),即dp(i,j-v[i]),即此时和我们原来的方程不等价, 原方程为dp(i-1,j-v[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
31
32
33
34
35
36
37
38
import java.util.Scanner;

public class Main{
    public static void main(String[] args) throws Exception {
      
        Scanner reader = new Scanner(System.in);
    
        int N = reader.nextInt();
        
        int V = reader.nextInt();
       
        int[] v = new int[N + 1] ;
      
        int[] w = new int[N + 1] ;

        for (int i=1 ; i <= N ; i++){
          
            v[i] = reader.nextInt();
            w[i] = reader.nextInt();
        }
        reader.close() ;

        
        int[] dp = new int[V+1];
        dp[0]= 0;
        for(int i = 1; i <= N; i++){
          //即我们只是改变了这里的遍历顺序，便可以优化空间复杂度
            for(int j = V; j >=v[i] ;j--){
                if(j >= v[i]){
                    dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
                }else{
                    dp[j] = dp[j];
                }
            }
        }
        System.out.println(dp[V]);
    }
}

至此，我们就实现了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
import java.util.Scanner;

public class Main{
    public static void main(String[] args) throws Exception {
      
        Scanner input = new Scanner(System.in);
    
        int N = input.nextInt();
        
        int V = input.nextInt();
       
        int[] v = new int[N + 1] ;
      
        int[] w = new int[N + 1] ;

        for (int i=1 ; i <= N ; i++){
          
            v[i] = input.nextInt();
            w[i] = input.nextInt();
        }
      

        
        int[] dp = new int[V+1];
        dp[0]= 0;
        for(int i = 1; i <= N; i++){
          //与01背包不同的是，我们只改变了这一行代码，即改变j的遍历顺序
            for(int j = v[i]; j <=V ;j++){
                if(j >= v[i]){
                    dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
                }else{
                    dp[j] = dp[j];
                }
            }
        }
        System.out.println(dp[V]);
    }
}

事实上，我们只改变了一行代码，但是01背包与多重背包却有着很大的不同！

01背包与完全背包的区别在于，一个背包可以重复选

  • 此时我们还是和分析01背包一样，考虑两个子问题， 即最后一个背包选或者不选，不选的情况和上述01背包一样.
  • 区别在于，如果我们选择最后一个背包，我们可以选1个，2个…k个….. 一只到满足背包的容量.
  • 即dp(i,j)=max{dp(i-1,j),dp(i-1,j-v)+w,dp(i-1,j-2v)+2w…..dp(i-1,j-kv)+kw} 此时max里面有n个值，如果对n个值进行比较，我们需要再添加一层for循环，即O(n^3)的时间复杂度，显然是不可取的.
  • 此时我们做一个变量替换，dp(i,j-v)=max{dp(i-1,j-v),dp(i-1,j-2v)+w,dp(i-1,j-3v)+w……..}
  • 相信你已经看到了，上下两个式子非常相似，只相差一个W，即我们需要求dp(i,j)的最大值，只需要求dp(i,j-v)的最大值+w
  • 即dp(i,j)=max{dp(i-1,j),dp(i,j-v)+w}

通过上述的转移方程，我们可以很容易的写出代码

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
import java.util.Scanner;

/**
 * 
 * dp[i][j]=Math.max(dp[i-1][j],dp[i][j-v[i]]+w[i])
 **/
public class Main{
    public static void main(String[] args) throws Exception {
      
        Scanner reader = new Scanner(System.in);
    
        int N = reader.nextInt();
        
        int V = reader.nextInt();
       
        int[] v = new int[N + 1] ;
      
        int[] w = new int[N + 1] ;

        for (int i=1 ; i <= N ; i++){
          
            v[i] = reader.nextInt();
            w[i] = reader.nextInt();
        }
        reader.close() ;

       int dp[][]=new int[N+1][V+1];
       dp[0][0]=0;
       for(int i=1;i<=N;i++){
           for(int j=0;j<=V;j++){
               if(j-v[i]>=0) dp[i][j]=Math.max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
               else dp[i][j]=dp[i-1][j];
           }
       }
       System.out.println(dp[N][V]);
    }
}

如果要对这个二维数组进行优化，与上述思路一样，并且此时 j-v<j，即此时dp(j-v[i])就是在第i层算出来的，即等价于dp(i,j-v[i])，那么我们此时可以直接进行优化

1
2
3
4
5
6
7
 for(int i=1;i<=N;i++){
           for(int j=v[i];j<=V;j++){
               if(j-v[i]>=0) dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
               else dp[j]=dp[j];
           }
       }
System.out.println(dp[V]);

至此，01背包与完全背包也就全部写完了！

赏

谢谢你请我喝奶茶

微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家