01背包问题

1.题目

2.思路分析

先来理解一下题意，假如你来到了一个藏宝洞前，然后手里有一个背包，面前有很多金银珠宝，数量为 n，而你的背包容量有限为 v，你想怎么装，价值最大。

那么定义一个二维数组 f[i][j] ，其含义是前 i 个物品里体积不超过 j且价值最大的集合。

既然集合有了，那么如何求这个最大值呢，我们把这个背包分为两种情况，包含第 i个物品，和不包含第 i个物品，首先考虑不包含的情况下，那么这个数组价值最大值应该是 f[i-1][j] 而包含i的数组无法直接求，这时候采取曲线救国,他的价值应该是不包含 i的情况下的最大值加上 i的价值，即 f[i][j] =f[i-1][j-v[i] ] +w[i] ,前提是 j 比 v[i]要大，那么这个时候的最大值就出来了 f[i][j] =max( f[i-1][j] ,f[i-1][j-v[i] ] +w[i]

3.完整代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    static int N=1010;
    static int []v=new int[N];   //体积
    static int []w=new int[N];   //价值
    static int [][]f=new int[N][N];  //在体积 j内前 i个物品的最大价值
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String []s=br.readLine().split(" ");
        int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]);
        for (int i = 1; i <=n; i++) {
            String []s1=br.readLine().split(" ");
            v[i]=Integer.parseInt(s1[0]);
            w[i]=Integer.parseInt(s1[1]);
        }
        for (int i = 1; i <=n; i++) {
            for (int j = 1; j <=m; j++) {
                f[i][j]=f[i-1][j]; //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
                if(j>=v[i]) {
                    f[i][j]=Math.max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(f[n][m]);
    }
}

4.代码优化（二维变一维）

二维转化为一维：

删掉了第一维：在前i个物品中取。

f[j]表示：拿了总体积不超过j的物品，最大总价值。

为何能转化为一维？

二维时的更新方式：f[i][j] =max( f[i - 1][j] , f[i - 1][j - v[i]] + w[i]);

1.我们发现，对于每次循环的下一组i，只会用到 i-1 来更新当前值，不会用到 i-2及之前值。于是可以在这次更新的时候，将原来的更新掉，反正以后也用不到。

所以对于 i的更新，只需用一个数组，直接覆盖就行了。

2.我们发现，对于每次 j的更新，只需用到之前 i-1时的 j或者 j-v[i]，不会用到后面的值。

所以为了防止串着改，我们采取从后往前更新的方式，用原来 i-1的数组来更新i。

（如果从前往后更新的话，前面的更新过之后，会接着更新后面的值，这样就不能保证是用原来i-1的数组来更新i的了）

如何转化为一维呢？

只用一个数组，每次都覆盖前面的数组。

1.如果当前位置的东西不拿的话，和前一位置的信息（原来i-1数组的这个位置上的值）是相同的，所以不用改变。

2.如果当前位置的东西拿了的话，需要和前一位置的信息（原来i-1数组的这个位置上值）取max。

所以，更新方式就为： f[j]=max( f[j], f[ j- v[i] ]+ w[i]);

整个更新方式就相当于：

每次i++，就从后往前覆盖一遍f数组，看每个位置上的值是否更新。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int N=1010;
    static int n,m;
    static int []v=new int[N];   //体积
    static int []w=new int[N];   //价值
    static int []f=new int[N];  //拿了总体积不超过j的情况下的价值最大
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s[]=br.readLine().split(" ");
        n=Integer.parseInt(s[0]);
        m=Integer.parseInt(s[1]);
        for (int i = 1; i <=n; i++) {
          String st[]=br.readLine().split(" ");
          v[i]=Integer.parseInt(st[0]);
          w[i]=Integer.parseInt(st[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] );
            }
        }
        System.out.println(f[m]);
    }
}

完全背包问题

1.题目

2.思路分析

思路和01背包相同，只是现在一个物品可以取多次了，那么就加次循环，模拟被取多次

3.完整代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int N=1010;
    static int n,m;
    static int []v=new int[N];   //体积
    static int []w=new int[N];   //价值
    static int [][]f=new int[N][N];  //拿了总体积不超过j的情况下的价值最大
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s[]=br.readLine().split(" ");
        n=Integer.parseInt(s[0]);
        m=Integer.parseInt(s[1]);
        for (int i = 1; i <=n; i++) {
          String st[]=br.readLine().split(" ");
          v[i]=Integer.parseInt(st[0]);
          w[i]=Integer.parseInt(st[1]);
        }
        for (int i = 1; i <=n; i++) {
            for (int j = 1; 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]);
    }
}

4.代码优化

我们列举一下更新次序的内部关系：

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)

f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)

由上两式，可得出如下递推关系：

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

有了上面的关系，那么其实k循环可以不要了，核心代码优化成这样：

for (int i = 1; i <=n; i++) {
for (int j = 1; 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]);
}
}

这个代码和01背包的非优化写法很像啊!!!我们对比一下，下面是01背包的核心代码

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[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]); //完全背包问题

因为和01背包代码很相像，我们很容易想到进一步优化。核心代码可以改成下面这样

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

综上所述，完全背包的最终写法如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int N=1010;
    static int n,m;
    static int []v=new int[N];   //体积
    static int []w=new int[N];   //价值
    static int []f=new int[N];  //拿了总体积不超过j的情况下的价值最大
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s[]=br.readLine().split(" ");
        n=Integer.parseInt(s[0]);
        m=Integer.parseInt(s[1]);
        for (int i = 1; i <=n; i++) {
          String st[]=br.readLine().split(" ");
          v[i]=Integer.parseInt(st[0]);
          w[i]=Integer.parseInt(st[1]);
        }
        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]);
    }
}

5时间复杂度

感谢你能看完，如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下

动态规划——01背包问题、完全背包问题

01背包问题

1.题目

2.思路分析

3.完整代码

4.代码优化（二维变一维）

完全背包问题

1.题目

2.思路分析

3.完整代码

4.代码优化

5时间复杂度

热门文章

最新文章

相关电子书