Обмен технологиями

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

один,Двумерный массив

1、уравнение перехода состояний：

• Не размещайте предметы : выводится из dp[i - 1][j], то есть вместимость рюкзака равна j и максимальное значение предмета i в него не помещается. В этот момент dp[i][j] равен dp[i -. 1][дж]. (Фактически, когда вес предмета i превышает вес рюкзака j, предмет i нельзя положить в рюкзак, поэтому его ценность в рюкзаке остается такой же, как и раньше.)
• Поместите пункт я: Выводится из dp[i - 1][j - вес[i]], dp[i - 1][j - вес[i]] — это максимальная вместимость рюкзака без предмета i, когда вместимость равна j - вес[ i] значение, тогда dp[i - 1][j - вес[i]] + значение[i] (значение предмета i) — это максимальное значение, полученное при помещении предмета i в рюкзак

Итак, рекурсивная формула: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - вес[i]] + значение[i]);

2. Инициализация

(1) Исходя из определения dp[i][j], если вместимость рюкзака j равна 0, то есть dp[i][0], независимо от того, какие предметы выбраны, общая стоимость рюкзака должна быть равна 0.

(2) Уравнение перехода состояний dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - вес[i]] + значение[i]); Видно, что i является производным от i-1, поэтому его необходимо инициализировать, когда i равно 0.

dp[0][j], то есть: i равно 0, при хранении предмета с номером 0 — максимальное значение, которое может хранить рюкзак каждой вместимости.

Тогда очевидно, что когда j < вес[0], dp[0][j] должно быть равно 0, поскольку вместимость рюкзака меньше веса предмета с номером 0.

Когда j >= вес[0], dp[0][j] должно быть значением[0], поскольку вместимости рюкзака достаточно, чтобы вместить предмет номер 0.

for (int j = 0 ; j < weight[0]; j++) {
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

(3) Другая инициализация индекса:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - вес[i]] + значение[i])

dp[1][1] = max(dp[0][1], dp[0][1- вес[i]] + значение[i]) должно находиться левее и выше него,

Следовательно, он должен быть инициализирован и ему может быть присвоено любое значение. Для удобства по умолчанию оно инициализируется значением 0.

2. Одномерный (скользящий массив)

1. В одномерном массиве dp dp[j] означает: рюкзак вместимостью j может нести предметы с максимальным значением dp[j]

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

2. Инициализация

(1) dp[0]=0, поскольку максимальное количество предметов, переносимых в рюкзаке вместимостью 0, равно 0.

(2) Предположим, что значение элементов больше 0,Чтобы не быть перезаписанным начальным значением, так что дпИнициализация массиваКогда они все изначально равны 0

3. Порядок обхода

Траверс в обратном порядке

Пояснение 1: Значение в конце списка необходимо определить путем сравнения его с предыдущим значением, полученным при прохождении предыдущего уровня.

Пояснение 2: Для каждого рюкзака имеется только один рюкзак 01. Размещена эта сумка или нет, зависит от статуса предыдущей сумки. Массив слева представляет собой количество, описывающее состояние предыдущей сумки, и число. справа — ожидающий статус текущей сумки. В коде число слева требуется для определения массива справа, поэтому число слева не может быть уничтожено до того, как будет вычислено число справа.

Объяснение 3: Для двух измерений результат каждого нового числа dp, который у меня есть, идет сверху и слева, на самом деле так должно быть в одном измерении, но в одном измерении, если оно все еще слева направо, то; мой фактический левый Цифры обновлены ( Левая сторона больше не является «оригинальной» левой стороной!Это приведет к двойному счету ), даже если вершина по-прежнему остается исходной, полученное число неверно.А если мы пройдемся справа налево по слою рюкзака (внутреннему слою), то элемент слева всегда будетОн не будет перезаписан новыми значениями из-за моей предыдущей операции., чтобы можно было получить правильное значение.

3. Приложение

1. Дан непустой массив, содержащий только положительные целые числа. Можно ли разбить этот массив на два подмножества так, чтобы сумма элементов двух подмножеств была равна?

Примечание. Число элементов в каждом массиве не превышает 100, а размер массива не превышает 200.

Пример 1:

• Ввод: [1, 5, 11, 5]
• Вывод: правда
• Пояснение: Массив можно разделить на [1, 5, 5] и [11].

анализировать:

Товар - я,

Вес — nums[i], значение — также nums[i], а объём рюкзака — sum/2.

Похоже на: 01 рюкзак

Уравнение перехода состояний:

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) {
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) return true;

2. Имеется куча камней, вес каждого камня — целое положительное число.

В каждом раунде выбирайте любые два камня и разбивайте их вместе. Предположим, что веса камней равны x и y соответственно, и x <= y. Тогда возможные результаты дробления будут следующими:

Если x == y, то обе породы будут полностью раздавлены;

Если x != y, то камень веса x полностью разобьется, а камень веса y будет иметь новый вес yx.

В конце концов, останется максимум один камень. Возвращает наименьший возможный вес этого камня. Если камней не осталось, верните 0.

Пример:

• Ввод: [2,7,4,1,8,1]
• Выход: 1

анализировать:

Постарайтесь разделить камни на две кучки одинакового веса так, чтобы самый маленький камень, оставшийся после столкновения,

Затем разделите его на две кучки камней. Общий вес одной кучки камней равен dp[target], а общий вес другой кучки равен sum — dp[target].

При вычислении цели цель = сумма / 2, поскольку она округляется в меньшую сторону, поэтому сумма - dp[цель] должна быть больше или равна dp[цель]

Тогда минимальный вес камня, оставшегося после столкновения, равен (сумма - dp[цель]) - dp[цель]

for (int i = 0; i < stones.length; i++) {
//采用倒序
    for (int j = target; j >= stones[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}
//结果
sum - 2 * dp[target];

цитируется по:Код случайных заметок