英文:
dp[!t][val] for skipping the parts from array
问题
考虑以下来自动态规划教程的 C++ 代码片段，主要用于优化空间的背包问题：
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 部分用于跳过当前项
}
}
此代码摘自这个 教程。我想将这个技术转换成 Java。但是 Java 不支持这种类型的整数操作。请问有人可以解释一下它是如何工作的，并给出适当的 Java 转换方法吗？谢谢。
英文:
consider the following snippet in cpp. This is taken from dynamic programming tutorial .
It is mainly for space optimized knapsack problem.
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
}
}
This snippet is taken from this tutorial. I want to convert this technique into java. But java does not support this type of integer manipulation. Please can anyone explain me how it works and appropriate conversion to java ? thanks.
答案1
得分: 1
只需将 !t 替换为 t ^ 1 或 1 - t（无论哪种方式更易读; 效果相同）。这是您在这里需要做的全部。
解释
Java 支持在此代码片段中显示的所有整数操作：
int t = a % 2; <-- 这在 Java 中是有效的，并且在 Java 中与在 C 中的意思相同：将 a 除以 2，并将 余数 放入 t，保留 a 的符号。因此：如果 a 是偶数，则 t 现在为 0；如果 a 是正奇数，则 t 为 1；如果 a 是负奇数，则 t 为 -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; 或用 Math.min 替换 min 以使其工作。
dp[!t] <-- !t 不是有效的 Java；但是，在 C 中，运行 !t，其中 t 是 0 或 1，只是翻转事物：如果 t 是 1，则 !t 为 0，反之亦然。您可以在 Java 中轻松实现此操作：使用 t ^ 1 或 1 - t，甚至可以使用 t == 0 ? 1 : 0 - 所有这些行为完全相同且是有效的 Java。
英文:
Just replace !t with t ^ 1 or 1 - t (whatever you find more readable; the effect is the same). That's all you need to do here.
Explanation
Java supports all the integer manipulation on display in this snippet:
int t = a % 2; <-- this is valid java and means the same thing in java as it does in C: divide a by 2, and put the remainder in t, preserving the sign of a. Thus: t is now 0 if a was even, and 1 if a was positive and odd, and -1 if a was negative and odd. It looks like a is supposed to be positive in this scenario, meaning that t can only be 0 or 1 here.
dp[t][j] <-- valid java. Declare dp as for example int[][] dp = new int[100][100];.
min(someExpression, someOtherExpression) <-- valid java; add import static java.lang.Math.min; or replace min with Math.min to make it work.
dp[!t] <-- the !t isn't valid java; but, in C, running !t where t is either 0 or 1 is just flipping things: If t is 1, !t is 0, and vice versa. And that you can trivially do in java: Use t ^ 1 or 1 - t or even t == 0 ? 1 : 0 – all have the exact same behaviour and are valid java.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论