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

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.

Answer

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.