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.

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.

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.

## Recent Comments