精华内容
下载资源
问答
  • 省公司提出“以客户价值化、网络价值化、管理价值化、人才价值化和伙伴价值化为工作主线,确保持续稳健增长,全力打造价值型企业”的新思路。 同时市公司提出了“客户捆绑低额度、长周期、不重复、多渠道、高渗透 ”...
  • 在使用一数组解决 0-1 背包问题的基础上,讲解如何解决完全背包、多重背包、分组背包、背包具体方案 和 有依赖的背包问题 … 0-1 背包问题 0-1 背包问题 :有 N 件物品和一个容量为 C 的背包。第 i 件物品的费用是...

    前言

    本文将从最简单的 0-1 背包问题出发,讲解如何将相应解法从 O(N * C)O(N∗C) 的空间复杂度降到 O©O© 。

    在使用一维数组解决 0-1 背包问题的基础上,讲解如何解决完全背包、多重背包、分组背包、背包具体方案 和 有依赖的背包问题 …

    0-1 背包问题

    0-1 背包问题 :有 N 件物品和一个容量为 C 的背包。第 i 件物品的费用是 v[i],价值是 w[i]。

    求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

    0-1 背包问题是众多背包问题中最简单的,其特点是物品不能重复放入。

    定义状态:即 f[i][C] 表示前 i 件物品放入一个容量为 C 的背包可以获得的最大价值。

    状态转移方程为:

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

    即对于第 i 件物品,我们有两种决策方案:

    不选择第 i 件物品,则最大价值等于f[i - 1][C],全部容量留给前 i - 1件物品
    选择第 i 件物品,则最大价值等于 w[i] + f[i - 1][C - v[i]] ,其中 w[i] 代表当前物品的价值,这样就用掉了v[i]的体积,留给前i - 1件物品的容量就剩下C - v[i],所以总的价值等于w[i] + f[i - 1][C - v[i]]

    0-1 背包问题的dp[N][C + 1]解法

    根据状态转移方程,我们可以建立一个二维的 dp 数组来存储结果。

    第一维代表物品的下标(范围从 0 到 N - 1),第二维代表了容量的变化(范围从 0 到 C)。
    参考文章
    并得知 base case dp[0][0] 的初始值为 0,原问题的解在 dp[N - 1][C] 的格子里面。

    import java.util.Scanner;
    public class Main{ 
        public static void main(String[] args){ 
            Scanner sc = new Scanner(System.in); 
            int N = sc.nextInt(); 
            int C = sc.nextInt(); 
            int[] v = new int[N]; 
            int[] w = new int[N]; 
            for (int i = 0; i < N; i++){ 
                v[i] = sc.nextInt(); 
                w[i] = sc.nextInt(); 
            }
            System.out.println(maxValue(N, C, v, w)); 
        }
    
        private static int maxValue(int N, int C, int[] v, int[] w) {
            int[][] dp = new int[N][C + 1];
            dp[0][0] = 0;
            for (int i = 0; i < C + 1; i++) {
                dp[0][i] = i >= v[0] ? w[0] : 0;
            }
            for (int i = 1; i < N; i++) {
                for (int j = 0; j < C + 1; j++) {
                    int n = dp[i - 1][j]; // 不选该物品
                    int y = 0;
                    if (j >= v[i]) {
                        y = w[i] + dp[i - 1][j - v[i]]; // 选择该物品
                    }
                    dp[i][j] = Math.max(n, y);
                }
            }
            return dp[N - 1][C];
        }
    }//加入Java开发交流君样:756584822一起吹水聊天
    

    该算法的时空复杂度均为 O(N * C)O(N∗C) 。

    我们使用的「动态规划」本质也是一种枚举,所以在时间复杂度上已经没有优化空间了(枚举需要对每一种可能性进行统计)。

    0-1 背包问题的 dp[2][C + 1] 解法

    根据状态转移方程,我们可以知道计算某个格子的值,只需要依赖前一行(计算第 i 行格子只需要第 i - 1 行中的某些值)。

    所以可以用一个只有两行的数组来存储中间结果,根据当前计算的行号是偶数还是奇数来交替使用第 0 行和第 1 行。

    import java.util.Scanner;
    public class Main{ 
        public static void main(String[] args){ 
            Scanner sc = new Scanner(System.in); 
            int N = sc.nextInt(); 
            int C = sc.nextInt(); 
            int[] v = new int[N]; 
            int[] w = new int[N]; 
            for (int i = 0; i < N; i++){ 
                v[i] = sc.nextInt(); 
                w[i] = sc.nextInt(); 
            }
            System.out.println(maxValue(N, C, v, w)); 
        }
    
        private static int maxValue(int N, int C, int[] v, int[] w) {
            int[][] dp = new int[2][C + 1];
            dp[0][0] = 0;
            for (int i = 0; i < C + 1; i++) {
                dp[0][i] = i >= v[0] ? w[0] : 0;
            }
            for (int i = 1; i < N; i++) {
                for (int j = 0; j < C + 1; j++) {
                    int n = dp[(i - 1)%2][j]; // 不选该物品
                    int y = 0;
                    if (j >= v[i]) {
                        y = w[i] + dp[(i - 1)%2][j - v[i]]; // 选择该物品
                    }
                    dp[i%2][j] = Math.max(n, y);
                }
            }//加入Java开发交流君样:756584822一起吹水聊天
            return dp[(N - 1)%2][C];
        }
    }
    

    这样我们就把算法的空间复杂度从O(N * C)O(N∗C) 降低为 O(C)O(C)

    再次观察状态转移方程,我们发现当求解第 i 行格子的值的时候,不仅是只依赖第 i - 1 行,而且是明确只依赖第 i - 1 行的第 C 个格子和第C - v[i]个格子(也就是对应着第 i 个物品不选和选的两种情况)。

    0-1 背包问题的 dp[C + 1] 解法

    也就是说明确只依赖于 「上一个格子的位置」 以及 「上一个格子的左边位置」。

    当我们将求解第 i 行格子顺序从 0 到 C 改为从 C 到 0,我们可以将原本 2 行的二维数组压缩到一行(转换为一维数组)。

    import java.util.Scanner;
    public class Main{ 
        public static void main(String[] args){ 
            Scanner sc = new Scanner(System.in); 
            int N = sc.nextInt(); 
            int C = sc.nextInt(); 
            int[] v = new int[N]; 
            int[] w = new int[N]; 
            for (int i = 0; i < N; i++){ 
                v[i] = sc.nextInt(); 
                w[i] = sc.nextInt(); 
            }
            System.out.println(maxValue(N, C, v, w)); 
        }
    //加入Java开发交流君样:756584822一起吹水聊天
        private static int maxValue(int N, int C, int[] v, int[] w) {
            int[] dp = new int[C + 1];
            for (int i = 0; i < C + 1; i++) {
                dp[i] = i >= v[0] ? w[0] : 0;
            }
            for (int i = 1; i < N; i++) {
                for (int j = C; j >= 0; j--) {
                    int n = dp[j]; // 不选该物品
                    int y = 0;
                    if (j >= v[i]) {
                        y = w[i] + dp[j - v[i]]; // 选择该物品
                    }
                    dp[j] = Math.max(n, y);
                }
            }
            return dp[C];
        }
    }
    

    这样,当我们处理第 i 行的第 j 个格子的时候,访问的 dp[j] 和 dp[j - v[i]]其实是第 i - 1 行的结果。

    然后通过比较之后,选择当中的最大值更新到 dp[j],这时候才代表第 i 行第 j 个格子被更新了。

    这就是我们使用一维数组解决 0-1 背包问题的解法。

    它的时间复杂度仍然是O(N * C)O(N∗C),但空间复杂度已经降为了O(C)O(C)。

    和 0-1 背包问题的dp[2][C + 1]解法 的空间复杂度一样,都是O(C)O(C),但是相应的常数降低了,从 2C 降为 C。

    使用的是一维 dp,在处理第 i 行之前,数组装的都是第 i - 1 行的结果,所以可以对循环内部的判断进行简化:
    参考文章

    import java.util.Scanner;
    public class Main{ 
        public static void main(String[] args){ 
            Scanner sc = new Scanner(System.in); 
            int N = sc.nextInt(); 
            int C = sc.nextInt(); 
            int[] v = new int[N]; 
            int[] w = new int[N]; 
            for (int i = 0; i < N; i++){ 
                v[i] = sc.nextInt(); 
                w[i] = sc.nextInt(); 
            }
            System.out.println(maxValue(N, C, v, w)); 
        }
    
        private static 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 = w[i] + dp[j - v[i]]; // 选择该物品
                    dp[j] = Math.max(n, y);
                }
            }
            return dp[C];
        }
    }
    

    当 j 不满足 j >= v[i] 的时候,注定无法选择第 i 个物品,这时候的 dp[i] 应该是等于 dp[i - 1]。

    因为使用的是一维数组,dp[i] 本身就是装着 dp[i - 1] 的值,所以无须再进行修改。

    这和使用二维 dp 的方式不同,使用二维 dp 就算当前 j 比 v[i] 要小,也要把上一行的 dp[i - 1][j] 的结果拉下来,赋值给 dp[i][j] 。

    同时也是因为使用的是一维 dp,没有了访问 dp[i - 1][j] 这样的操作,也不需要先处理第 0 行,可以直接让循环从 i = 0 开始。

    如何用一维 dp 来解决 0-1 背包十分重要,其他背包问题一定程度上都能转化成 0-1 背包来进行求解 或是 根据 0-1 背包的转移方程来稍作修改。

    完全背包问题

    完全背包问题 : 有 N 种物品和一个容量为 C 的背包,每种物品都有无限件。

    第 i 件物品的体积是 v[i],价值是 w[i]。

    求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

    其实就是在 0-1 背包问题的基础上,增加了每件物品可以选择多次的特点(在容量允许的情况下)。

    状态转移方程 & 时间复杂度分析
    根据和 0-1 背包问题的基本思路,我们可以写成如下的状态转移方程:

    f[i][C] = max(f[i - 1][C- k*v[i]] + k * w[i]), 0 <= k * v[i] <= c
    f[i][C]=max(f[i−1][C−k∗v[i]]+k∗w[i]),0<=k∗v[i]<=c
    

    该式子很好理解,k * v[i] 为 0 的时候代表不选当前的第 i 件物品,这时候有 f[i][C] = f[i - 1][C] ,当k * v[i]不为 0 的时候,代表第 i 件物品可能会被选择多次。

    这时候二维 dp 的表格大小依然是N * C的,但是求解某个格子的值的时候,并不是单纯的比较上一行的两个格子,而是要比较多个格子。

    要比较的格子数量不确定,比较格子的数量等于最多可选第 i 件物品多少次,也就是(C / v[i]) + 1个。

    这里的 C 为当前格子的容量,不是总容量,加一代表还要比较不选择第 i 个格子的情况),按照最坏的时间复杂度计算,最多要比较 C + 1 个格子,也就是上一行的 0 ~ C 的格子全部都要进行比较。

    这时候计算某个格子的值不再是常数操作。时间复杂度为O(N * C * C)O(N∗C∗C) 。

    完全背包问题的常规解法

    import java.util.Scanner;
    public class Main{ 
        public static void main(String[] args){ 
            Scanner sc = new Scanner(System.in); 
            int N = sc.nextInt(); 
            int C = sc.nextInt(); 
            int[] v = new int[N]; 
            int[] w = new int[N]; 
            for (int i = 0; i < N; i++){ 
                v[i] = sc.nextInt(); 
                w[i] = sc.nextInt(); 
            }
            System.out.println(maxValue(N, C, v, w)); 
        }
    //加入Java开发交流君样:756584822一起吹水聊天
        private static 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--) {
                    for (int k = 0 ;; k++) {
                        if (j < v[i] * k) {
                            break;
                        }
                        dp[j] = Math.max(dp[j], dp[j - v[i] * k] + w[i] * k);
                    }
                }
            }
            return dp[C];
        }
    }
    

    我们在处理第 j 个格子的时候,某件物品可以不选或者选到超出容量限制为止(反映了完全背包问题物品可以选择无限次的特点)。由此我们得出了完全背包问题的常规解法,它的时间复杂度是大于 O(N * C)O(N∗C)的。

    利用 0-1 背包的一维 dp 方法求解完全背包
    我们掌握了如何通过一维 dp 解决 0-1 背包问题,只需要将求解第 i 行格子(逻辑上的第 i 行,物理上是一维的)的顺序从 C 到 0 改回从 0 到 C 即可。

    import java.util.Scanner;
    public class Main{ 
        public static void main(String[] args){ 
            Scanner sc = new Scanner(System.in); 
            int N = sc.nextInt(); 
            int C = sc.nextInt(); 
            int[] v = new int[N]; 
            int[] w = new int[N]; 
            for (int i = 0; i < N; i++){ 
                v[i] = sc.nextInt(); 
                w[i] = sc.nextInt(); 
            }
            System.out.println(maxValue(N, C, v, w)); 
        }
    
        private static 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--) { // 0-1 背包问题
                for (int j = v[i]; j <= C; j++) { // 完全背包问题
    
                    int n = dp[j]; // 不选该物品
                    int y = w[i] + dp[j - v[i]]; // 选择该物品
                    dp[j] = Math.max(n, y);
                }
            }
            return dp[C];
        }
    }
    

    j的处理顺序改为从小到大,这样就保证当我们使用 dp[j - v[i]]时,该值是已经被计算过的。

    这样所代表的状态含义是:当在容量为 j 的时候,考虑将 i 物品加入,剩余的 j - v[i]容量也考虑加入物品 i(反映了完全背包问题的物品是可以被重复选择的特点)。

    完全背包问题的一维 dp 解法的数学证明

    前面所说的「将 j 的处理顺序改为从小到大,这样就保证当我们使用 dp[j - v[i]]时,该值是已经被计算过的」,是我们利用抽象思维去理解这样的做法。

    但感觉不一定是对的。

    我们尝试从数学的角度去证明为什么 dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i] 在完全背包问题中是正确的。

    首先我们将状态转移方程退回去最朴素的二维解法中。

    也就是用一维代表当前决策的是前 i 个物品,用一维代表当前的容量为 j。这时候根据完全背包中物品的选择次数是无限的。

    可以得出:

    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i], dp[i - 1][j - 2 * v[i]] + 2 * w[i] ... dp[i - 1][j - k * v[i] + k * w[i]]),0 <= k * v[i] <= j
    dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i],dp[i−1][j−2∗v[i]]+2∗w[i]...dp[i−1][j−k∗v[i]+k∗w[i]]),0<=k∗v[i]<=j
    

    dp[i][j]对应的就是:面对第 i 件物品,可以不选,可以选 1 次,可以选 2 次 …

    在容量允许的情况下,不失一般性的可以选 k 次 …

    然后再来看看 dp[i][j - v[i]] 是什么内容:

    dp[i][j - v[i]] = max(dp[i - 1][j - v[i]], dp[i - 1][j - 2 * v[i]] + w[i], dp[i - 1][j - 3 * v[i]] + 2 * w[i] ... dp[i - 1][j - k * v[i] + (k - 1 )* w[i]]),0 <= k * v[i] <= j
    dp[i][j−v[i]]=max(dp[i−1][j−v[i]],dp[i−1][j−2∗v[i]]+w[i],dp[i−1][j−3∗v[i]]+2∗w[i]...dp[i−1][j−k∗v[i]+(k−1)∗w[i]]),0<=k∗v[i]<=j
    

    光看公式可能很难看出两者的联系,我们将相同的部分进行标记:

    总结一下,0-1 背包问题的状态转换方程是 1,完全背包问题的状态转移方程是 2:

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

    两者仅仅是 dp[i - 1][j - v[i]] 和 dp[i][j - v[i]]的区别,这一区别决定了 j 的遍历顺序。

    虽然完全背包问题的实现上和 0-1 背包相比,只是在对 j 的遍历方向上进行修改。

    但能这样做原因是因为有严谨的数学证明推导,而不是凭感觉抽象理解。

    彻底转换为 0-1 背包问题

    对于完全背包,我们知道每件物品可以选择无限次,但是我们的容量仍然是有限的。

    这就意味着对于每件物品而言,我们选择范围为 0~C/v[i],要么一件不选,要么所有容量都用来装这同一件物品。

    我们可以新建一个物品数组,对于第 i 件物品,往物品数组放入C/v[i] 件,第 i + 1 件物品,则放入C/v[i + 1]件 …

    从而将一个完全背包问题彻底转换为 0-1 背包问题。

    这样的做法不会降低我们的复杂度,反而增加了我们转换背包问题时所带来的常数级别的复杂度成本,所以不对该做法进行展开。

    我们是可以采用「二进制数」的思路来优化,但它优化完的复杂度仍然是大于O(N * C)O(N∗C)的,所以我们将这个优化思路放到「多重背包问题」里去讲。

    这样的做法仍然很有意义,它给我们提供了一个思路:将一种物品拆成多件物品,从而将其他背包问题彻底转换为 0-1 背包进行求解。

    多重背包问题

    多重背包问题 I :有 N 种物品和一个容量是 V 的背包。

    第 i 种物品最多有s[i]件,每件体积是v[i],价值是w[i]

    求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。

    其实就是在 0-1 背包问题的基础上,在容量允许的情况下,增加了每件物品可以选择多次的特点(但又不是无限次,是有限制的多次)。

    所以我们还是在 0-1 背包的基础上进行分析。

    状态转移方程 & 时间复杂度分析

    既然对每件物品有选择数量上的限制,这意味着选择的数量 k 需要满足 0 <= k <= s[i]。

    能够很清晰的分析出状态转移方程:

    f[i][C] = max(f[i - 1][C - k*v[i]] + k * w[i]), 0 <= k * v[i] <= C, 0 <= k <= s[i]
    f[i][C]=max(f[i−1][C−k∗v[i]]+k∗w[i]),0<=k∗v[i]<=C,0<=k<=s[i]
    

    将 s[i] 按照最坏复杂度计算,这时候算法复杂度应该是 O(N * C * C)O(N∗C∗C)。

    多重背包问题的常规解法
    我们可以基于 0-1 背包问题的一维 dp 解法,增加一个循环,从 0 开始遍历 s[i]。

    得出以下的常规解法:

    import java.util.Scanner;
    class Main {
        public static void main(String[] arg) {
            Scanner sc = new Scanner(System.in); 
            int N = sc.nextInt(); 
            int C = sc.nextInt(); 
            int[] v = new int[N]; 
            int[] w = new int[N]; 
            int[] s = new int[N];
            for (int i = 0; i < N; i++){ 
                v[i] = sc.nextInt(); 
                w[i] = sc.nextInt(); 
                s[i] = sc.nextInt(); 
            }
            System.out.println(maxValue(N, C, s, v, w)); 
        }
    
        private static 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];
        }
    }
    

    多重背包问题的「二进制优化」解法

    多重背包问题 II :题目和「多重背包问题 I」完全一样,只是数据范围从 百级 上升到 千级 。

    所谓的「二进制优化」其实是指,我们如何将一个多重背包问题彻底转化为 0-1 背包问题,同时降低其复杂度。

    0-1 背包问题讲的是物品列表里面的每个物品只能选择一次,而这里的多重背包问题则是每个物品有最大数量限制,所以我们可以将其进行「扁平化」。

    如果第 i 件物品有 s1 件,则将 s1 个 i 物品放到物品列表;如果第 i + 1 件物品有 s2 件,则将 s2 件 i + 1 物品放到物品列表。

    物品列表里面的每个物品有选和不选两种选择,这样就对应了多重背包问题中的每样物品可以不选或最多选择 s[i] 的特性。

    从而将一个多重背包问题彻底转换为 0-1 背包问题。

    但是光进行这样的「扁平化」并不能降低算法的复杂度。

    因为我们仍然要处理这么多的物品,反而增加了将物品「扁平化」的工作量。

    算法的复杂度在常数级别上是上升的。这样做的意义在哪?

    我们现在采取的「扁平化」策略是直接展开,一个数量为 10 的物品等效于 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 。

    这样并没有减少运算量,但是如果我们能将 10 变成小于 10 个数,那么这样的「扁平化」就是有意义的。

    学过 Linux 的都知道文件权限最高是 7,代表拥有读、写、执行的权限。

    但其实这个 7 是对应了 1、2、4 三个数字的,也就是 r : 1、w : 2、x : 4 ,三种权限的组合共有 8 种可能性。

    这里就采用了 3 个数来对应 8 种情况的“压缩”方法。我们也可以借鉴这样的思路,将原本为 n 的物品用 ceil(log(n)) 个数来代替。从而降低算法复杂度。

    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。

    来看看通过「扁平化」来解决多重背包问题的代码:
    参考文章

    import java.util.*;
    class Main {
        public static void main(String[] arg) {
            Scanner sc = new Scanner(System.in); 
            int N = sc.nextInt(); 
            int C = sc.nextInt(); 
            int[] v = new int[N]; 
            int[] w = new int[N]; 
            int[] s = new int[N];
            for (int i = 0; i < N; i++){ 
                v[i] = sc.nextInt(); 
                w[i] = sc.nextInt(); 
                s[i] = sc.nextInt(); 
            }
            System.out.println(maxValue(N, C, s, v, w)); 
        }
    
        private static int maxValue(int N, int C, int[] s, int[] v, int[] w) {
            // 扁平化
            List<Integer> worth = new ArrayList<>();
            List<Integer> 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];
        }
    }
    

    这时候算法的时间复杂度为O(∑log S[i] * C)O(∑logS[i]∗C)

    这时候的∑log S[i]∑logS[i] 为 S 数组里的物品数量进行二进制展开后的总和。

    相比于原本为O(∑S[i] * C)O(∑S[i]∗C)的时间复杂度要下降不少。

    多重背包问题的「单调队列」解法

    多重背包问题 III :题目和「多重背包问题 I」完全一样,只是数据范围从 百级 上升到 万级 。

    在「多重背包问题 I」的朴素解法中,我们是先循环物品(范围 0 ~ N - 1),再循环容量(范围 0 ~ C),再循环每件物品可以选择的次数(范围 0 ~ s[i] )。

    import java.util.*;
    class Main {
        public static void main(String[] arg) {
            Scanner sc = new Scanner(System.in); 
            int N = sc.nextInt(); 
            int C = sc.nextInt(); 
            int[] v = new int[N]; 
            int[] w = new int[N]; 
            int[] s = new int[N];
            for (int i = 0; i < N; i++){ 
                v[i] = sc.nextInt(); 
                w[i] = sc.nextInt(); 
                s[i] = sc.nextInt(); 
            }
            System.out.println(maxValue(N, C, s, v, w)); 
        }
    
        private static int maxValue(int N, int C, int[] s, int[] v, int[] w) {
            int[] dp = new int[C + 1];
            int[] g = new int[C + 1]; // 辅助队列,记录的是上一次的结果
            int[] q = new int[C + 1]; // 主队列,记录的是本次的结果
    
            // 枚举物品
            for (int i = 0; i < N; i++) {
                int vi = v[i];
                int wi = w[i];
                int si = s[i];
                // 将上次算的结果存入辅助数组中
                g = dp.clone();
    
                // 枚举余数
                for (int j = 0; j < vi; j++) {
                    int hh = 0, tt = -1;
                    // 枚举同一余数情况下,有多少种方案。例如余数为 1 的情况下有:1、vi + 1、2 * vi + 1、3 * vi + 1 ...
                    for (int k = j; k <= C; k+=vi) {
                        dp[k] = g[k];
                        if (hh <= tt && q[hh] < k - si * vi) hh++;
                        if (hh <= tt) dp[k] = Math.max(dp[k], g[q[hh]] + (k - q[hh]) / vi * wi);
                        while (hh <= tt && g[q[tt]] - (q[tt] - j) / vi * wi <= g[k] - (k - j) / vi * wi) tt--;
                        q[++tt] = k;
                    }
                }
            }
            return dp[C];
        }
    }
    

    在多重背包的单调队列解法中,除了用于保存答案的 dp 数组以外,我们要需要两个数组 g 和 q 来充当队列。

    先枚举所有的物品,在枚举每件物品的时候取出该物品的体积 vi 、价值 wi 和数量 si;同时将 dp 中的内容复制到队列中(就是将前 i - 1 件物品的计算结果从 dp 复制到队列 g 中)
    再枚举每个余数,由于当前物品的体积为 vi,因此余数范围在 [0, vi) 左闭右开区间中;同时在计算每个余数的时候重新初始化两个队列(重置队列头下标 hh 和队列尾下标 tt)
    再枚举在某个余数的情况下,有多少方案。例如余数为 1 的情况下有:

    1、vi + 12 * vi + 13 * vi + 1 ..
    

    dp[k] = g[k];:首先将上一次的计算结果存入

    if (hh <= tt && q[hh] < k - si * vi) hh++;

    将队列头部中不合法的元素移除(将 hh 往前移动)

    if (hh <= tt) dp[k] = Math.max(dp[k], g[q[hh]] + (k - q[hh]) / vi * wi); 
    

    :更新 dp[k],在原来的答案 dp[k] 和 g[q[hh]] + (k - q[hh]) / vi * wi)
    之间取最大值,g[q[hh]] + (k - q[hh]) / vi * wi) 其实就是dp[j - k * v] + k * w的展开式,此时有 q[hh] = j - k * v, j = k while (hh <= tt && g[q[tt]] - (q[tt] - j) / vi * wi <= g[k] - (k - j) / vi * wi) tt--;:维护队列的单调性
    q[++tt] = k; :将 k 入队

    混合背包问题

    混合背包问题 :其实就是 0-1 背包、完全背包 和 多重背包 的混合版本。

    仍然是给定物品数量 N 和背包容量 C。第 i 件物品的体积是 v[i],价值是 w[i],可用数量为 s[i]。

    当 s[i] 为 -1 代表是该物品只能用一次;当 s[i] 为 0 代表该物品可以使用无限次;当 s[i] 为任意正整数则代表可用 s[i] 次。

    求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

    s[i] 的几种状态就对应了 0-1 背包、完全背包 和 多重背包。

    我们知道 0-1 背包问题将当前容量 j 从大到小遍历,而完全背包则是将当前容量 j 从小到大遍历,多重背包可以用过「二进制优化」彻底转移成 0-1 背包问题。

    它们的状态转移方程都一样,所以我们只需要根据第 i 个物品是 0-1 背包物品还是完全背包问题,选择不同的遍历顺序即可。

    import java.util.*;
    class Main {
        public static void main(String[] arg) {
            Scanner sc = new Scanner(System.in); 
            int N = sc.nextInt(); 
            int C = sc.nextInt(); 
            int[] v = new int[N]; 
            int[] w = new int[N]; 
            int[] s = new int[N];
            for (int i = 0; i < N; i++){ 
                v[i] = sc.nextInt(); 
                w[i] = sc.nextInt(); 
                s[i] = sc.nextInt(); 
            }
            System.out.println(maxValue(N, C, s, v, w)); 
        }
    
        private static int maxValue(int N, int C, int[] s, int[] v, int[] w) {
            List<Integer> worth = new ArrayList<>();
            List<Integer> volume = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                int type = s[i];
                if (type > 0) { // 将多重背包问题转换为 0-1 背包问题
                    for (int k = 1; k <= type; k *= 2) {
                        type -= k;
                        worth.add(w[i] * k);
                        volume.add(v[i] * k);
                    }
                    if (type > 0) {
                        worth.add(w[i] * type);
                        volume.add(v[i] * type);
                    }
                } else if (type == -1) {
                    worth.add(w[i]);
                    volume.add(v[i]);
                } else { // 对于完全背包,将 worth 翻转,用作标记
                    worth.add(-w[i]);
                    volume.add(v[i]);
                }
            }
    
            int[] dp = new int[C + 1];
            for (int i = 0; i < worth.size(); i++) {
                int wor = worth.get(i);
                int vol = volume.get(i);
                if (wor < 0) { // 完全背包问题
                    for (int j = vol; j <= C; j++) {
                        dp[j] = Math.max(dp[j], dp[j - vol] - wor); // 将 worth 重新翻转为正整数
                    }
                } else { // “原 0-1 背包物品” 或 “由多重背包转移过来的 0-1 背包问题”
                    for (int j = C; j >= vol; j--) {
                        dp[j] = Math.max(dp[j], dp[j - vol] + wor);
                    }
                }
            }
            return dp[C];
        }
    }
    

    就这样我们解决了这个混合背包问题。

    先将一个多重背包问题根据「二进制优化」的思路,转化为 0-1 背包问题,然后根据物品是属于 0-1 背包 还是 完全背包 决定容量 j 是从大到小还是从小到大进行推算。

    换句话说就是根据物品的类型不同,选择不同的转移方式。

    多维背包问题

    多维背包问题 :有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。

    每件物品只能用一次,第 i 件物品的体积是 v[i],重量是 m[i],价值是 w[i]。

    求解将哪些物品装入背包可使这些物品的重量和体积总和都不超过限制,且价值总和最大。

    上面所说的背包问题都只有“体积”这么一个限制条件,而多维背包问题是指物品同时会有多个限制条件,如该例的重量。

    但由于每件物品都只能用一次,其实本质还是一个 0-1 背包问题,只是做法在从前基础上(维度表示体积)增加一维(一个维度代表体积,一个维度代表重量)。

    相应的(完整)状态转移方程也很好得出:

    f[i][C][M] = max(f[i - 1][C][M], f[i - 1][C - v[i]][M - m[i]] + w[i])
    f[i][C][M]=max(f[i−1][C][M],f[i−1][C−v[i]][M−m[i]]+w[i])
    

    和之前几个背包问题一样,我们可以将 i (代表物品下标的)这一维消掉,因为我们在决策第 i 个物品的时候只依赖于决策第 i - 1 个物品时的结果,配合着从大到小的处理顺序,我们可以只用“一个单位”的维度装下所有我们需要的结果。

    在多维背包问题中“一个单位”就是指只包含限制条件的多维 dp,对应到该题就是 dp[C][M]。
    参考文章

    import java.util.*;
    class Main {
        public static void main(String[] arg) {
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int V = sc.nextInt();
            int M = sc.nextInt();
            int[] v = new int[N];
            int[] m = new int[N];
            int[] w = new int[N];
            for (int i = 0; i < N; i++) {
                v[i] = sc.nextInt();
                m[i] = sc.nextInt();
                w[i] = sc.nextInt();
            }
            System.out.println(maxValue(N, V, M, v, m, w));
        }//加入Java开发交流君样:756584822一起吹水聊天
    
        private static int maxValue(int N, int C, int M, int[] v, int[] m, int[] w) {
            int[][] dp = new int[C + 1][M + 1];
            for (int i = 0; i < N; i++) {
                for (int j = C; j >= v[i]; j--) {
                    for (int k = M; k >= m[i]; k--) {
                        dp[j][k] = Math.max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]);
                    }
                }
            }
            return dp[C][M];
        }
    }
    

    二维背包问题是通过增加维度来解决,其他多维背包问题也是同理,都是通过增加维度来解决问题,转移方程不变。事实上,当发现由熟悉的动态规划题目变形得来的题目时,在原来的状态中加维度以满足新的限制是一种比较通用的方法。

    分组背包问题

    分组背包问题 :有 N 组物品和一个容量为 C 的背包。

    每组物品有若干个,同一组内的物品最多只能选一个。

    每件物品的体积是 v[i][j],价值是 w[i][j],其中 i 是组号,j 是组内编号。

    求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

    import java.util.*;
    class Main {
        public static void main(String[] arg) {
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int V = sc.nextInt();
            int[] S = new int[N];
            int[][] v = new int[N][];
            int[][] w = new int[N][];
            for (int i = 0; i < N; i++) {
                int si = sc.nextInt();
                S[i] = si;
                int[] vol = new int[si];
                int[] wor = new int[si];
                for (int j = 0; j < si; j++) {
                    vol[j] = sc.nextInt();
                    wor[j] = sc.nextInt();
                }
                v[i] = vol;
                w[i] = wor;
            }
            System.out.println(maxValue(N, V, S, v, w));
        }
    
        private static 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++) {
                int[] vol = v[i];
                int[] wor = w[i];
                int si = S[i];
                for (int j = C; j >= 0; j--) {
                    for (int k = 0; k < si; k++) {
                        if (j >= vol[k]) {
                            dp[j] = Math.max(dp[j], dp[j - vol[k]] + wor[k]);   
                        }
                    }
                }
            }
            return dp[C];
        }
    }
    

    背包问题具体方案数

    背包问题求方案数 :有 N 件物品和一个容量是 C 的背包。

    每件物品只能使用一次。

    第 i 件物品的体积是 v[i],价值是 w[i]。

    求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最优选法的方案数。

    import java.util.*;
    class Main {
        private static final int mod = 1000000007;
        public static void main(String[] arg) {
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int V = sc.nextInt();
            int[] v = new int[N];
            int[] w = new int[N];
            for (int i = 0; i < N; i++) {
                v[i] = sc.nextInt();
                w[i] = sc.nextInt();
            }//加入Java开发交流君样:756584822一起吹水聊天
            System.out.println(combineCount(N, V, v, w));
        }
    
        private static int combineCount(int N, int C, int[] v, int[] w) {
            // 构建一个 dp 数组,除了第一位为 0,其他位均为 Integer.MIN_VALUE
            int[] dp = new int[C + 1];
            for (int i = 1; i <= C; i++) dp[i] = Integer.MIN_VALUE;
    
            // 再构建一个 g 数组来存储不同容量下的方案数,除了第一位为 1,其他位均为 0
            int[] g = new int[C + 1];
            g[0] = 1;
    
            for (int i = 0; i < N; i++) {
                for (int j = C; j >= v[i]; j--) {
                    int val = Math.max(dp[j], dp[j - v[i]] + w[i]);
                    int cnt = 0;
    
                    // val 有可能等于 dp[j],有可能等于 dp[j - v[i]] + w[i],也有可能都等于
                    // 如果 val 为 dp[j],增加 g[j]
                    if (val == dp[j]) cnt += g[j];
                    // 如果 val 为 dp[j - v[i]] + w[i],增加 g[j - v[i]]
                    if (val == dp[j - v[i]] + w[i]) cnt += g[j - v[i]];
                    // 采用更为“高效”的取余方法
                    if (cnt >= mod) cnt -= mod;
    
                    dp[j] = val;
                    g[j] = cnt;
                }
            }
    
            int max = 0;
            for (int i = 0; i <= C; i++) max = Math.max(max, dp[i]);
            int ans = 0;
            for (int i = 0; i <= C; i++) {
                if (dp[i] == max) {
                    ans += g[i];
                    if (ans >= mod) ans -= mod;
                }
            }
            return ans;
        }
    }
    

    这个解法有点啰嗦,但这是个更为通用的解法。

    不仅可以求最大容量时的方案数,还能求具体某个容量时的方案是,只需要将最后一个循环中所使用的 max 变量修改为目标容量即可。
    参考文章

    背包问题具体方案

    背包问题求具体方案 :有 N 件物品和一个容量是 C 的背包。

    每件物品只能使用一次。

    第 i 件物品的体积是 v[i],价值是 w[i]。

    求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。求字典序最小的具体方案。

    这里的字典序是指:所选物品的编号所构成的序列 1 … N 。

    由于求背包最大价值时的状态f[i][j]定义是:考虑前 i 件物品,容量不超过体积 j 的情况下,得到的最大价值。

    状态转移方程是f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w) ,也就是每一个f[i][j]都是由对于第 i 件物品的决策而来:选择第 i 件物品或不选择第 i 件物品。

    所以可以将f[i][j]f[i - 1][j] 、f[i - 1][j - v] + w 进行比较,得出f[i][j]是由选择还是不选择第 i 件物品转移过来的。

    总结一下,就是根据以下逻辑来“反推”具体方案数:

    仅满足 f[i][j] == f[i - 1][j] :f[i][j]是由不选择第 i 件物品转移过来,物品 i 不在具体方案数里面
    仅满足 f[i][j] == f[i - 1][j - v] + w :f[i][j]是由选择第 i 件物品转移过来的,物品 i 在具体方案里面
    满足f[i][j] == f[i - 1][j] == f[i - 1][j - v] + w :f[i][j]即可以由选择第 i 件物品转移过来,也可以由不选择第 i 件物品转移过来,由于求的是最小方案数,所以能选择靠前的物品的话,尽量选择。当物品编号从小到大顺序遍历时,可选可不选的情况,则选。物品 i 在具体方案里面
    为了方便我们能够按物品编号从小到大顺序 遍历得到具体方案数,最好让 f[1][C] 为最大价值,也就是在计算最大价值的时候我们应该按照从 N … 1 的顺序进行递推。

    具体代码如下:

    import java.util.*;
    class Main {
        static int N = 1010;
        static int C = 1010;
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int c = sc.nextInt();
            int[] wi = new int[N];
            int[] vi = new int[N];
            for (int i = 1; i <= n; i++) {
                vi[i] = sc.nextInt();
                wi[i] = sc.nextInt();
            }
            int[][] f = new int[N][C];
            // 从 N ... 1 的顺序进行考虑
            for (int i = n; i >= 1; i--) {
                for (int j = 0; j <= c; j++) {
                    f[i][j] = f[i + 1][j];
                    if (j - vi[i] >= 0) {
                        f[i][j] = Math.max(f[i][j], f[i + 1][j - vi[i]] + wi[i]);
                    }
                }
            }
    
            // System.out.print(f[1][c]); // 最大价值
    
            int t = c;
            // 从 1 ... N 反推具体方案
            for (int i = 1; i <= n; i++) {
                int v = vi[i];
                int w = wi[i];
                if (t >= v && f[i][t] == f[i + 1][t - v] + w) {
                    System.out.print(i + " ");                
                    t -= v;
                }
            }
        }//加入Java开发交流君样:756584822一起吹水聊天
    }
    

    有依赖的背包问题

    有依赖的背包问题 :有 N 个物品和一个容量是 V 的背包。

    物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。


    如果选择物品 5,则必须选择物品 1 和 2。这是因为 2 是 5 的父节点,1 是 2 的父节点。

    每件物品的编号是 i,体积是 v[i],价值是 w[i],依赖的父节点编号是 p[i]。
    物品的下标范围是 1 … N。

    求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

    该题本质是一道树形 dp 题,可以通过递归求解。同时每颗子树又能视为一个分组背包来求解:

    import java.util.*;
    class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int C = sc.nextInt();
            int[] V = new int[N];
            int[] W = new int[N];
            int[] P = new int[N];
            for (int i = 0; i < N; i++) {
                V[i] = sc.nextInt();
                W[i] = sc.nextInt();
                P[i] = sc.nextInt();
            }
            int ans = maxValue(N, C, V, W, P);
            System.out.println(ans);
        }
    
        private static int maxValue(int N, int C, int[] V, int[] W, int[] P) {
            // dp[x][v]:选择以 x 为子树的物品,在容量不超过 v 时所获得的最大价值
            int[][] dp = new int[N][C + 1];
    
            // 建立一个数组,每个下标存放对应 “以该下标为父节点” 的所有子节点(root 节点的编号为 1)
            // 该数组下标为 0 的存放的是 root 节点,下标为 1 存放的是以 root 节点为父节点的结点 ...
            List<Integer>[] tree = new List[N + 1]; 
            Arrays.setAll(tree, e -> new ArrayList<Integer>());
            int root = -1;
            for (int i = 0; i < N; i++) {
                if (P[i] == -1) {
                    root = i;  
                } else {
                    tree[P[i]].add(i); 
                }
            }
    
            // dfs 求解
            dfs(N, C, V, W, dp, root, tree);
            //加入Java开发交流君样:756584822一起吹水聊天
            // 最终答案是以 root 为子树(代表了 root 本身也是可以被选或不选)、容量不超过 C 的最大价值
            return dp[root][C];
        }
    
        private static void dfs(int N, int C, int[] V, int[] W, int[][] dp, int root, List<Integer>[] tree) {
            int vi = V[root];
            int wi = W[root];
            for (int i = vi; i <= C; i++) {
                dp[root][i] = wi;
            }
            List<Integer> child = tree[root + 1]; // root 的编号为 1
            int size = child.size();
            for (int i = 0; i < size; i++) {
                int node = child.get(i);
                dfs(N, C, V, W, dp, node, tree);
                for (int j = C; j >= vi; j--) {
                    for (int k = 0; k <= j - vi; k++) {
                        dp[root][j] = Math.max(dp[root][j], dp[root][j - k] + dp[node][k]);
                    }
                }
            }
        } 
    }
    

    总结

    几乎所有的背包问题,都是先遍历物品,再遍历容量,最后再遍历决策(在遍历决策里可能又是通过循环实现)。

    背包问题的本质其实是这么一个模型:我有一些额度(背包容量)用来做决策(选择物品),做决策会伴随着成本和收益,求解在额度以内的最大收益。

    所有的背包问题的变种都离不开这个模型。

    另外根据不同的状态定义,可以采取不同的初始化的策略:

    状态定义为考虑前 i 件物品,体积最多(不超过)为 j 的话:全部初始化为 0,递推过程保证体积大于等于 0
    状态定义为考虑前 i 件物品,体积恰好为 j 的话:只有f[0][0]初始为 0,其他为正无穷,递推过程保证体积大于等于 0
    状态定义为考虑前 i 件物品,体积至少为 j 的话:只有f[0][0]初始为 0,其他为正无穷,递推过程对体积没有要求,但负数的体积可以用体积为 0 来替代

    生命不止坚毅鱼奋斗,有梦想才是有意义的追求
    给大家推荐一个免费的学习交流君样:756584822
    最后,祝大家早日学有所成,拿到满意offer,快速升职加薪,走上人生巅峰。

    Java开发交流君样:756584822

    展开全文
  • 本文开发并实证测试了品牌价值模型。 更具体地说,这项研究从生产者的角度重新探讨了维度是如何形成和相互作用的。 本研究采用定量方法,使用基于协方差的结构方程模型(CB-SEM)探索品牌价值维度之间的逻辑关系。 ...
  • 结合灰色系统思想与神经网络的优点建立了一个灰色人工神经网络(Grey Artificial Neural Network,GANN)预测模型,对每一个指标分别用GM(1,1)模型选择最佳的数进行预测,再利用神经网络非线性映射的特性把这6 ...
  • 结合灰色系统思想与神经网络的优点建立了一个灰色人工神经网络(Grey Artificial Neural Network,GANN)预测模型,对每一个指标分别用GM(1,1)模型选择最佳的数进行预测,再利用神经网络非线性映射的特性把这6 ...
  • 理解多维数据模型价值、理解多维数据模型逻辑、理解透视分析原理、能够活用多维数据模型结合恰当透视方法观测业务问题实现商业洞察 1、多表透视分析逻辑(占比 3%) 【熟知】 熟知透视分析的作用价值 维度:行列...

    PART 5 多维数据透视分析占 比 10%

    总体要求

    理解多维数据模型价值、理解多维数据模型逻辑、理解透视分析原理、能够活用多维数据模型结合恰当透视方法观测业务问题实现商业洞察

    1、多表透视分析逻辑占比 3%

    【熟知】

    熟知透视分析的作用价值

    维度:行列标签

    理解多表环境下的连接、透视逻辑

    星型模式:由一个事实表和一组维度表组成,维度表只和事实表关联,维度表之间没有关联,以事实表为核心,维度表围绕核心呈星形分布。

              订单表、产品表与客户表:一个事实表连接两个维度表是星型模式

    雪花模式:雪花模型相当于将星形模式的大维度表拆分成小维度表,满足了规范化设计。多维表对应单事实表。

              订单表、产品表与品牌表:单表是事实表,展开产品与品牌两层维度表,展开多层维度是雪花模式

    星座模式:事实表不止一个,而一个维表也可能被多个事实表用到。

    交叉连接:   

    【应用】

    能够通过表的字段理解该表所代表的业务维度及业务意义,能够通过表的业务意义倒推回表中字段的主键、维度、度量属性

    主键的业务意义:表的业务记录单位


    2、多维数据模型占比 3%

    【领会】

    了解使用多维数据模型的业务意义

    【熟知】

    熟知多维数据模型的创建方法

    熟知多维数据模型中连接方式与汇总结果间的关系

    关键字段:主表附表都有,字段名不一定相同,但值要对应,不能有重复值

    横向合并:存放最终合并结果的表为主表;为主表提供必要信息的为附表

              当两表用于合并的关键字段值不是一一对应,不同连接种类会有不同的结果

              当关键字有重复值,连接后总行数为关键字段值重复出现次数的乘积   

    纵向合并:将有相同字段名的字段纵向合并到一起

              将不同字段名的字段追加到最后

              非匹配字段标记为null

    关键字段中有重复值的表为主表(*),无重复值的表为附表(1),在数据透视表中,只有当行列标签来自附表时,附表才能提供值字段,否则汇总值出现错误

    汇总原则:一表出维度,一对多的连接关系

    筛选器方向:单向:维度指向度量(维度筛选度量,箭头出发一侧为维度)

                         双向:两表间互为筛选

    谁出度量谁是主表   

    熟知多维数据模型下汇总维度与筛选维度间的差异及各自的适用场景

    【应用】

    能够通过 5W2H 思维模型梳理业务线索,搜集完整的多表数据。

    5W2H模型:what why who when where how how much

    能够根据业务需求,按照正确的连接关系创建完整、准确、全面的多维数据模型  能够根据多维数据模型推导出可探索的业务问题范围,实现业务洞察


    3、透视分析方法占比 4%

    【领会】

    透视分析的价值及意义

    【熟知】

    熟知基本透视规则:求和、求平均、计数、最大最小值

    熟知条件筛选透视规则:多条件透视计算、不同层级维度透视计算

    熟知基本对比计算规则:均比、基准比、标准比、百分比、差异百分比

    均比:实际值与平均值对比 同类型产品销售情况

    基准比:实际值与基准值之间的对比 成绩水平

    目标比:实际值与目标值之间对比 销售业绩绩效

    标准比:实际值与标准值对比 工场工作水平绩效

    占比:部分与总体对比 不同区域销售额占比

    熟知时间维度下的透视计算规则:不同时间段、不同时间位移量下的透视计算规则 

    熟知行间透视与字段上透视的差异

    【应用】

    能够根据业务需求选择创建正确的透视规则

    能够将透视规则应用在正确的多维模型下描述业务问题 能够通过透视结果理解业务问题

    透视结果与预期结果不符时,能够检查、追踪问题原因

    展开全文
  • Matlab关于蒙特卡洛仿真资料讲义和程序举例-第二讲-第讲.rar 看到有些同学在找这方面的资料,的确蒙特卡洛仿真在通信中的应用非常广泛,我把我现有的资料发给大家,希望对大家有用。 比较多,分成了几个压缩...
  • 本文用三维五层框架结构有限元模型数值模拟了四种 典型的损伤工况,损伤识别结果表明,应用本文所提的损伤定位因子可准确的对损伤构件实现损伤定位,相应得出 的损伤程度评估结果也与模拟的损伤工况较吻合。该方法不...
  • 使用了河口和湖Cmputer模型的三水动力模型,以数值模拟强潮条件,大气强迫和海洋条件的影响。 在所有计算单元中都计算了水年龄,并用公海的“纯”水在表层(潮汐和风的影响明显)以及更深层和底部的“纯”水进行...
  • 本文在考虑了振幅的横向分布和基波的衰减时,给出了一些关于倍频的有价值的结果。借助于求解三耦合波方程,导出了二次谐波功率的最一般的表达式,讨论了基波功率和晶体长度的影响。作为一个特例,也给出了低转换效率下...
  • 14,资金博弈分析综合多赢共振模型、多赢增仓模型量大模型,为投资者展示一个资金攻击思路,将投资分析从简单的一资金跟踪推向多维资金分析博弈。而多赢驱动是什么?多赢驱动就是资金博弈分析的监控功能。多赢量化...
  • 软件工程知识点

    2012-12-02 21:34:25
    (7)工程文化:包括工程价值、工程思想和工程行为三个方面的内容。 二、软件工程过程模型 1.软件生命周期 如同任何事物都有一个发生、发展、成熟直至衰亡的全过程一样,软件系统或软件产品也有一个定义、开发、...
  • 绝对有价值的一本书。 目录如下: 第一部分ActionScript动画基础 第1章 基本动画概念 1.1 什么是动画 1.2 帧和运动 1.2.1 帧就是记录 1.2.2 程序帧 1.3 动态动画 VS 静态动画小结 第2章ActionSript 3.0动画基础 2.1...
  • 说明:目前,数据分析是一个非常热门的方向,因为不管是互联网行业还是传统行业都已经积累了大量的数据,现在需要的就是从这些数据中提取有价值的信息,以便打造更好的产品或者为将来的决策提供支持。 给初学者的几...
  • 、K-Means聚类算法 1、聚类过程 2、目标函数 3、聚类中心的选择 4、聚类个数K的选择 5、应用——图片压缩 6、使用scikit-learn库中的线性模型实现聚类 7、运行结果 六、PCA主成分分析(降维) 1、用处 2、2D-...
  • asp.net知识库

    2015-06-18 08:45:45
    ASP.Net应用程序的多进程模型 NET委托:一个C#睡前故事 [推荐] - [原创] Microsoft .NET策略及框架概述 卸载Class? Web Form 窗体 如何实现web页面的提示保存功能 在ASP.Net中两种利用CSS实现多界面的方法 如何在...
  • 这些程序覆盖了Visual C++编程的主要应用:用户界面设计、多媒体(图形、图像、动画和声音)、网络(ActiveX组件、Internet、和数据库)以及杂类等大部分。其中,用户界面设计部分包括:按钮、编辑框、静态控件、组合...
  • 在统计学中,直方图(英语:Histogram)是一种对数据分布情况的图形表示,是一种二统计图表,它的两个坐标分别是统计样本和该样本对应的某个属性的度量。个变量,通常利用于较小的数据集分析。长条图亦可横向排列...
  • 它历经了 种种相悖结论 的一系列危机,直到 在20世纪期间 发掘出 作为具有多个方位或组成部分(集合论,模型论,证明论·····)的 一个庞大的、条理分明的 数学知识体系 而稳定下来。研究其详尽的属性和可能的...
  • IVD:超过20/20微观数据数或变量等级文件 IVP:超过20/20的用户子集配置文件 IVT:超过20/20表或集合数据文件 IVX:超过20/20微数据目录文件 IW:Idlewild屏幕保护程序 IWC:Install Watch文档 J J62:...
  • 2个目标文件 摘要:Java源码,网络相关,UDP 基于JAVA的UDP服务器模型源代码,内含UDP服务器端模型和UDP客户端模型两个小程序,向JAVA初学者演示UDP C/S结构的原理。 简单聊天软件CS模式 2个目标文件 一个简单的CS模式...
  • JAVA上百实例源码以及开源项目

    千次下载 热门讨论 2016-01-03 17:37:40
     基于JAVA的UDP服务器模型源代码,内含UDP服务器端模型和UDP客户端模型两个小程序,向JAVA初学者演示UDP C/S结构的原理。 简单聊天软件CS模式 2个目标文件 一个简单的CS模式的聊天软件,用socket实现,比较简单。 ...
  • ASP.NET精品课程+源代码

    千次下载 热门讨论 2009-01-05 20:15:51
    涵盖了代码规范、运行模型、服务控件、验证控件、数据绑定技术、ADO.NET技术、数据库技术、文件操作等内容。 所列出的内容均是ASP.NET开发网站等应用的必备知识。我们在实训课题引入的前提下,通过一系列完整的案例...
  • 数据仓库基础

    2012-03-29 13:25:26
    第一章对数据仓库的迫切需求...................................................................................................23 本章目标:.................................................................

空空如也

空空如也

1 2
收藏数 28
精华内容 11
关键字:

五维价值模型