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

Question

考虑 cpp 中的以下代码片段。这取自动态规划教程。

主要针对space优化的背包问题

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
    }
}

此片段摘自 tutorial。我想把这个技巧转化成java。但是 java 不支持这种类型的整数操作。请任何人都可以向我解释它是如何工作的以及如何适当地转换为 java 吗？谢谢。

Answer 1

只需将 !t 替换为 t ^ 1 或 1 - t（任何你觉得更易读的；效果是一样的）。这就是您需要做的全部。

说明

Java 支持此代码段中显示的所有整数操作：

int t = a % 2; <-- 这是有效的 java 并且在 java 中的含义与在 C 中的含义相同：将 a 除以 2，然后将 remainder in t，保留a的符号。因此：如果 a 是偶数，t 现在是 0，如果 a 是正奇数，1，如果 a 是负奇数，-1。看起来 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.

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

dp[!t][val] for skipping the parts from array

c++

java

knapsack-problem

dynamic-programming

说明