做网站信科网站建设,app网页设计网站,福田祥菱v1质量怎么样,抚州市临川区建设局网站1.多重背包问题 经典的多重背包问题和01背包问题的相似之处在于二者的一维遍历顺序都是从右侧往左侧遍历。
同时多重背包的一维写法不比二维写法降低时间复杂度。
2.多重背包标准写法:(平铺展开形式#xff09;
class Solution {public int maxValue(int N, int C, int[] s…1.多重背包问题 经典的多重背包问题和01背包问题的相似之处在于二者的一维遍历顺序都是从右侧往左侧遍历。
同时多重背包的一维写法不比二维写法降低时间复杂度。
2.多重背包标准写法:(平铺展开形式
class Solution {public int maxValue(int N, int C, int[] s, int[] v, int[] w) {int[] dp new int[C 1];for (int i 0; i N; i) {for (int j C; j v[i]; j--) {for (int k 0; k s[i] j k * v[i]; k) {dp[j] Math.max(dp[j], dp[j - k * v[i]] k * w[i]);}}}return dp[C];}
}
因为转换为一维之后无法记录每个物品的使用次数所以多重背包的一维写法并不能减低时间复杂度注意完全版背包的一维写法是能够降低时间复杂度的。此处的代码与01背包十分相似。01背包的代码如下:
class Solution {public int maxValue(int N, int C, int[] v, int[] w) {int[] dp new int[C 1];for (int i 0; i N; i) {for (int j C; j v[i]; j--) {// 不选该物品int n dp[j]; // 选择该物品int y dp[j-v[i]] w[i]; dp[j] Math.max(n, y);}}return dp[C];}
}
3.二进制压缩形式的多重背包
上述的多重背包的解法实际上是将带选择的m个物品平着展开为[1,1,1....](共计m个具体可以查看最后一个for循环的写法不断尝试一个一个的将数据加进去。
实际上这种解法只能解决数据量为平方级别的数据。而二进制解法则是将原本为 n 的物品用 ceil(log(n)) 个数来代替从而降低算法复杂度。
学过 Linux 的都知道文件权限最高是 7代表拥有读、写、执行的权限但其实这个 7 是对应了 1、2、4 三个数字的也就是 r:1、w:2、x:4 三种权限的组合共有 8 种可能性
7 可以用 1、2、4 来代替像刚刚提到的 10 我们可以使用 1、2、4、3 来代替你可能会有疑问为什么是 1、2、4、3而不是 1、2、4、6 或者 1、2、4、8 呢
其实把他们几个数加起来就知道了1、2、4、6 可以表达的范围是 0~13而 1、2、4、8 可以表达的范围是 0~15而我们要求的是表达 10大于 10 的范围是不能被选择的。
所以我们可以在 1、2、4 表达的范围是 0~7的基础上增加一个数 3由 10 - 7 而来这样就能满足我们需要表达的范围 0~10。
具体的转换为二进制的代码如下所示
class Solution {public int maxValue(int N, int C, int[] s, int[] v, int[] w) {// 扁平化ListInteger worth new ArrayList();ListInteger volume new ArrayList();// 我们希望每件物品都进行扁平化所以首先遍历所有的物品for (int i 0; i N; i) {// 获取每件物品的出现次数int val s[i];// 进行扁平化如果一件物品规定的使用次数为 7 次我们将其扁平化为三件物品1*重量1*价值、2*重量2*价值、4*重量4*价值// 三件物品都不选对应了我们使用该物品 0 次的情况、只选择第一件扁平物品对应使用该物品 1 次的情况、只选择第二件扁平物品对应使用该物品 2 次的情况只选择第一件和第二件扁平物品对应了使用该物品 3 次的情况 ... //注意此处是等号可能正好减完for (int k 1; k val; k * 2) { val - k;worth.add(w[i] * k);volume.add(v[i] * k);}if (val 0) {//没有正好减完worth.add(w[i] * val);volume.add(v[i] * val);}}// 0-1 背包问题解决方案int[] dp new int[C 1];for (int i 0; i worth.size(); i) {for (int j C; j volume.get(i); j--) {dp[j] Math.max(dp[j], dp[j - volume.get(i)] worth.get(i));}}return dp[C];}
}
