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

Question

我在这里查看这个 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]能给出结果吗？

据我所知，他们正在尝试所有可能的组合/组合。我感到困惑的是(即使在执行并主演了一个多星期之后):

他们如何跟踪所有组合？

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

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

Answer 1

cost, keep cost at each step, some sort of dynamic programming?

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

I don't understand how cost[1 << n] can give the result?

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

how do they keep track of all the combinations?

见下文。这与cost的原因密切相关。数组被声明为它的大小。

I understand pre - is the cost of the previous monster defeated (i.e. how much cost we incurred there), but I don't understand how you get it from just (i - 1 << j).

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

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

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

这里的技巧是一个相对常见的技巧，也是一个值得了解的技巧。假设您有一组 N 个对象，并且您希望以某种方式表示其所有子集(== 其元素的所有不同组合)。每个子集的特征在于 N 个对象中的每一个是否是元素。您可以将其表示为 N 个数字，每个数字可以是 0 或 1——即 N 位。现在假设您将这些位串在一起形成 N 位数字。从 0(含)到 2^N(不含)的每个整数都有其最低有效 N 位的不同模式，因此每个整数对应于不同的子集。

所提供的代码正是使用这种对应关系将 Boss 集合的不同子集编码为 cost 中的不同索引。数组——它回答了你的另一个问题，即它如何跟踪组合。给定一个这样的索引 i表示包含 boss j 的子集，索引i - (1 << j)表示去掉boss后得到的集合j .

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