背包问题

有N件物品和一个最大分量为W的背包，每件物品分量weight[i]，价值是value[i]。每件物品只能取一次，背包能保留的最大价值是多少？ 动静布局五部曲： a) 确定dp数组以及下标的含意 b) 确定递推公式 c) dp数组的初始化 d) 确定遍历程序 e) 举例推导dp数组 解题思路： 1) 确定dp数组以及下标的含意 dp[i][j]的定义为：从0~i的物品中任意取，背包容量为j的状况下价值总和最大是dp[i][j] 2) 递推公式 dp[i][j]从逻辑剖析上来看，有两个起源：即不放入物品i，那么dp[i][j] = dp[i-1][j]（表明在j容量下，物品i所占分量对应的价值小于0~i-1物品中选取的其余价值）。放入物品i，dp[i][j] = value[i] + dp[i-1][j-weight[i]] 最终得出dp[i][j]取上述两种起源的最大值。 公式：dp[i][j] = Max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]]) 3) dp数组初始化 依据dp数组的定义，背包容量为0时，最大价值永远为0。dp[i][0] = 0 依据递推公式可知，i取决于i-1，所以要对i=0时的状态做初始化。也就是只寄存物品0时，各个背包容量下的最大价值dp[0][j] 编码： 第一层循环物品，第二层循环背包容量 public static int packageOneOrZero(int[] weights, int[] values, int packageWeight) { // 定义dp[i][j]示意 从0~i的物品中任意放入容量为j的背包，最大价值总和为dp[i][j] int[][] dp = new int[values.length][packageWeight + 1]; // dp[0][j]初始化 for (int j = packageWeight; j >= weights[0]; j--) { dp[0][j] = dp[0][j - weights[0]] + values[0]; } for (int i = 1; i < values.length; i++) { for (int j = 0; j <= packageWeight; j++) { if (j < weights[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Math.max(dp[i - 1][j - weights[i]] + values[i], dp[i - 1][j]); } } } return dp[values.length - 1][packageWeight]; } public static void main(String[] args) { int[] weights = new int[] {1, 3, 4}; int[] values = new int[] {15, 20, 30}; System.out.println(packageOneOrZero(weights, values, 4));}简化思路：将i-1和i进行合并，即应用一维数组进行运算 ...

1. 01背包01背包是所有简单背包的根底，把握了对前面更简单的背包了解有很大的帮忙；背包问题物品只能拿和不拿，最多拿一次，用来动静布局的办法，先上论断：动静布局方程式:参数阐明： dp是指背包最大价值j指最大背包容量i指的是以后正在放入背包的第i件物品，w[i]指以后放入物品的分量v[i]指以后放入物品的价值。dp[j]=max(dp[j], dp[j-w[i]]+v[i])上面是计算程序，能够失去一张动静规划表，依据不同物品数量、不同背包容量取得不同的后果let m = 10 //背包容量let n = 4 //物品数量const w = [0, 3, 4, 5, 6] //物品分量const v = [0, 3, 5, 3, 8] //物品价值//dp数组，后果寄存的不同背包容量的最大价值const dp = []// 按程序放入物品for (i = 1;i <= n;i++) { // 不同背包容量，顺叙，因为数组右边的值是上一条数据最为条件，计算出当条的后果寄存在左边，最初更新整个数组 for (j = m;j >= 1; j--) { if (j >= w[i]) dp[j] = max(dp[j], dp[j-w[i]] + v[i]) } for (k = 1; k <= m; k++) { console.log(dp[k]) }}2. 齐全背包齐全背包惟一不同就是，物品能够有限次放进背包，其余条件和01背包一样，后果如下： ...