dp[!t][val]用于跳过数组中的部分。

Question

考虑以下cpp中的片段。这是从动态编程教程中摘录的，主要用于空间优化的knapsack问题。

它主要用于空间优化的knapsack问题。

for(int i=1;i<=a;i++)
{
    int t = a%2;
    for(int j=0;j<1100000;j++) dp[t][j]  = inf;
    for(int j=0;j<1100000;j++){
        dp[t][j] = min(dp[t][j],dp[!t][j-v[i-1]]+w[i-1]);//!t part is for skipping the current
    }
}

这个片段来自于这个 教程. 我想把这种技术转换到java中。但java不支持这种类型的整数操作。请谁能给我解释一下它是如何工作的，以及如何适当地转换到java中？ 谢谢。

Answer 1

替换成 !t 与 t ^ 1 或 1 - t (不管你觉得哪个更易读，效果都是一样的)。在这里你需要做的就是这些了。

解释

Java支持这个片段中显示的所有整数操作。

int t = a % 2; <--这是有效的java语言，在java中的意思和在C语言中的意思是一样的：把a除以2，然后把a除以2。剩余 的符号，保留 a. 因此。t 现在是0，如果 a 是平的，而且 1 如果a是正奇数，并且 -1 如果a是负数，而且是奇数。它看起来像 a 在这种情况下，应该是正数，即： t 只能 0 或 1 这里。

dp[t][j] <--有效的java。声明 dp 譬如 int[][] dp = new int[100][100];.

min(someExpression, someOtherExpression) <--有效的java；添加 import static java.lang.Math.min; 或将min改为 Math.min 以使其发挥作用。

dp[!t] <-- !t 并不是有效的java；但是，在C语言中，执行 !t 哪儿 t 是0或1都是翻天覆地的事情。如果 t 是1。!t 是0，反之亦然。你可以在java中简单地做到这一点。使用 t ^ 1 或 1 - t 甚至 t == 0 ? 1 : 0 - 所有的人都有相同的行为和 是 有效的java。