算法系列--动态规划--背包问题(3)--完全背包介绍（上）
https://developer.aliyun.com/article/1480854?spm=a2c6h.13148508.setting.14.5f4e4f0ewTpliD
💕"Su7"💕
作者：Lvzi
文章主要内容：算法系列–动态规划–背包问题(3)–完全背包介绍
大家好,今天为大家带来的是
算法系列--动态规划--背包问题(3)--完全背包介绍
代码:
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { // 1.解决第一问 Scanner in = new Scanner(System.in); int n = in.nextInt(), V = in.nextInt();// 获取物品数目和体积 int[] v = new int[n + 1], w = new int[n + 1]; for(int i = 1; i <= n; i++) { v[i] = in.nextInt();// 物品体积 w[i] = in.nextInt();// 物品价值 } int[][] dp = new int[n + 1][V + 1]; for(int i = 1; i <= n; i++) { for(int j = 1; j <= V; j++) { dp[i][j] = dp[i-1][j]; if(j - v[i] >= 0) dp[i][j] = Math.max(dp[i][j],dp[i][j - v[i]] + w[i]); } } System.out.println(dp[n][V]); // 1.解决第二问 dp = new int[n + 1][ V + 1];// 好的代码风格? for(int j = 1; j <= V; j++) dp[0][j] = -1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= V; j++) { dp[i][j] = dp[i - 1][j]; if(j - v[i] >= 0 && dp[i][j - v[i]] != -1) dp[i][j] = Math.max(dp[i][j],dp[i][j - v[i]] + w[i]); } } System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]); } }
空间优化:
同样的在完全背包问题中也可以进行空间优化(想想01背包问题中的空间优化,通过明确遍历顺序,只是用一个简单的线性数组就可以完成填表)
01背包问题的空间优化最需要注意的就是遍历顺序的改变,在01背包问题中,为了在填表的时候需要使用的数据不被覆盖掉,需要从右往左遍历,但是在完全背包问题中,需要从左往右遍历
空间优化后的代码:
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { // 1.解决第一问 Scanner in = new Scanner(System.in); int n = in.nextInt(), V = in.nextInt();// 获取物品数目和体积 int[] v = new int[n + 1], w = new int[n + 1]; for(int i = 1; i <= n; i++) { v[i] = in.nextInt();// 物品体积 w[i] = in.nextInt();// 物品价值 } int[] dp = new int[V + 1]; for(int i = 1; i <= n; i++) for(int j = v[i]; j <= V; j++) dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]); System.out.println(dp[V]); // 2.解决第二问 dp = new int[ V + 1];// 好的代码风格? for(int j = 1; j <= V; j++) dp[j] = -1; for(int i = 1; i <= n; i++) for(int j = v[i]; j <= V; j++) if(dp[j - v[i]] != -1) dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]); System.out.println(dp[V] == -1 ? 0 : dp[V]); } }
以上就是
算法系列--动态规划--背包问题(3)--完全背包介绍全部内容,下一篇文章将会带来完全背包问题的拓展题目,敬请期待,我是LvZi
