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时间复杂度
感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下
