dp [! t] [val] для пропуска частей из массива - PullRequest
Новая
       110

dp [! t] [val] для пропуска частей из массива

0 голосов
/ 04 мая 2020

рассмотрите следующий фрагмент в cpp. Это взято из динамического 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 part is for skipping the current
    }
}

Этот фрагмент взят из этого руководства . Я хочу преобразовать эту технику в java. Но java не поддерживает этот тип целочисленных манипуляций. Может кто-нибудь объяснить мне, как это работает и соответствующее преобразование в java? спасибо.

1 Ответ

2 голосов
/ 04 мая 2020

Просто замените !t на t ^ 1 или 1 - t (что вы считаете более читабельным; эффект тот же). Это все, что вам нужно сделать здесь.

Пояснение

Java поддерживает все целочисленные манипуляции, отображаемые в этом фрагменте:

int t = a % 2; <- это действительно java и означает то же самое в java, что и в C: разделите a на 2 и поместите остаток <em> в t, сохранив знак a. Таким образом: t теперь равно 0, если a было четным, и 1, если a было положительным и нечетным, и -1, если a было отрицательным и нечетным. Похоже, что a должен быть положительным в этом сценарии, а это означает, что t может быть только 0 или 1 здесь.

dp[t][j] <- действительно java. Объявите <code>dp как, например, int[][] dp = new int[100][100];.

min(someExpression, someOtherExpression) <- допустимый Java; добавьте <code>import static java.lang.Math.min; или замените min на Math.min, чтобы оно заработало.

dp[!t] <- <code>!t не является допустимым Java; но в C выполнение !t, где t - это либо 0, либо 1 - это просто переворачивание: если t равно 1, !t равно 0, и наоборот. И что вы можете сделать тривиально в java: используйте t ^ 1 или 1 - t или даже t == 0 ? 1 : 0 - все ведут себя точно так же, и действительны java.

...