时间戳

首页 > 解决方案 > 使用刚刚访问过的 int 变量通过矩阵查看不同的组合？

java - 使用刚刚访问过的 int 变量通过矩阵查看不同的组合？

问题描述

我在这里查看这个 topcoder 问题：

http://community.topcoder.com/tc?module=ProblemDetail&rd=4725&pm=2288

在 java 部分下有以下代码：

public class KiloManX {
    boolean ddd = false;

    int[] s2ia(String s) {
        int[] r = new int[s.length()];

        for (int i = 0; i < s.length(); i++) {
            r[i] = s.charAt(i) - '0' ;
        }
        return r;
    }

    public int leastShots(String[] damageChart, int[] bossHealth) {
        int i, j, k;
        int n = damageChart.length;
        int[][] dc = new int[n][];
        int[] cost = new int[1 << n];

        for (i = 0; i < n; i++) {
            dc[i] = s2ia(damageChart[i]) ;
        }
        for (i = 1; i < 1 << n; i++) {
            cost[i] = 65536 * 30000;

            for (j = 0; j < n; j++) {
                int pre = i - (1 << j);
                if ((i & (1 << j)) != 0) {
                    cost[i] = Math.min(cost[i], cost[pre] + bossHealth[j]) ;

                    for (k = 0; k < n; k++) {
                        if ((i & (1 << k)) != 0 && k != j && dc[k][j] > 0) {
                            cost[i] = Math.min(cost[i],
                                cost[pre] + (bossHealth[j] + dc[k][j] - 1) / dc[k][j]);
                        }
                    }
                }
            }
        }

        return cost[(1 << n) - 1] ;
    }

    static void pp(Object o) {
        System.out.println(o);
    }
}

我试图了解他做了什么。所以我的理解是：

  1. i- 以某种方式跟踪访问过的节点（这是代码中最令人困惑的部分）

  2. j- 是我们想要打败的怪物

  3. k- 是我们用来击败 j 的前一个怪物的武器
  4. dc是将字符串的输入数组转换为矩阵
  5. cost，保持每一步的成本，某种动态规划？我不明白如何cost[1 << n]给出结果？

我的理解是他们正在经历所有可能的集合/组合。我感到困惑的是（即使在执行并主演了一个多星期之后）是：

  1. 他们如何跟踪所有组合？
  2. 我明白pre- 是前一个怪物被击败的成本（即我们在那里产生了多少成本），但我不明白你是如何得到它的(i - 1 << j)。

我已经执行了程序（调试器），盯着它看了一个多星期，并试图对其进行解码，但我对代码的位操作部分感到困惑。有人可以解释一下吗？

标签： java

解决方案

cost，保持每一步的成本，某种动态规划？

它们是部分成本，是的，但是将它们描述为每步成本会忽略该数组中索引的最重要意义。更多内容如下。

我不明白如何cost[1 << n]给出结果？

当然，这本身并不会产生任何结果。它只是声明了一个包含 2 n 个元素的数组。

他们如何跟踪所有组合？

见下文。cost这与为什么将数组声明为它的大小密切相关。

我明白pre- 是前一个怪物被击败的成本（即我们在那里产生了多少成本），但我不明白你是如何从(i - 1 << j).

当然pre，它本身并不是成本。但是，它有条件地用作数组的索引。cost现在考虑条件：

                if ((i & (1 << j)) != 0) {

该表达式i & (1 << j)测试是否设置j了值的位i。当它是时，i - (1 << j)( ie pre ) 评估为关闭j的值的位的结果i。这应该会提示您的索引cost是位掩码。该数组 ( 1 << n) 的大小是另一个线索：它是不同n位掩码的数量。

这里的技巧是一个相对常见的技巧，也是一个很好知道的技巧。假设您有一组 N 个对象，并且您希望以某种方式表示其所有子集（== 其元素的所有不同组合）。每个子集的特征在于 N 个对象中的每个对象是否是一个元素。您可以将其表示为 N 个数字，每个数字为 0 或 1 -即N 位。现在假设您将这些位串成 N 位数字。从 0（包括）到 2 N（不包括）的每个整数都有其最低 N 位的不同模式，因此每个整数对应于不同的子集。

所提供的代码正是使用这种对应来将老板集的不同子集编码为cost数组中的不同索引——这回答了您关于它如何跟踪组合的另一个问题。给定一个i表示包含 boss 的子集j的索引，该索引i - (1 << j)表示通过删除 boss 从中获得的集合j。

粗略地说，程序通过检查所有方法来优化每个非空子集的成本，方法是检查从一个元素少的子集形成它的所有方法。 (1 << n) - 1是整个集合对应的索引，所以最后那个元素cost包含了整体优化值。

推荐阅读