В основном представляет проблему рюкзака 0-1 и некоторые решения проблем leetcode.
0-1 Проблема с рюкзаком
определение
Есть рюкзак, вместимость которого C (Вместимость). Теперь имеется n различных элементов с номерами 0...n-1, где каждый элемент имеет вес w(i) и значение v(i). Спросите, какие предметы можно положить в этот рюкзак, чтобы общая стоимость предметов была максимальной, но при этом не превышалась вместимость рюкзака.
Идеи решения проблем
Мы можем использовать рекурсию для решения таких комбинаторных задач. Это просто, можем ли мы найти в нем пересекающиеся подзадачи, а затем преобразовать оптимальную подструктуру в поиск в памяти или динамическое программирование для решения.
Для этой задачи у нас есть два ограничения
- Сначала мы должны выбрать среди n предметов
- Второй момент заключается в том, что его емкость должна быть меньше или равна заданному значению C.
определение состояния
Обратите внимание, что в этом вопросе для определения состояния используются две переменные.
F(n,C) рассматривает помещение n предметов в рюкзак вместимостью C, чтобы максимизировать ценность.
переход состояния
Для F(i,c) возможны два случая: добавление i-го элемента и прямое игнорирование i-го элемента.
F(i,C) = max{F(i-1, C), v(i) + F(i-1, C-w(i))}
Код
поиск памяти
class Knapsack01{
private:
vector<vector<int>> memo;
// 用 [0...index]的物品,填充容积为c的背包的最大价值
int bestValue(const vector<int> &w, const vector<int> v, int index, int c){
if( c <= 0 || index < 0 ) {
return 0;
}
if( memo[index][c] != -1 ) {
return memo[index][c];
}
int res = bestValue(w, v, index-1, c);
if( c >= w[index] ) {
res = max( res , v[index] + bestValue(w, v, index-1, c-w[index]) );
}
memo[index][c] = res;
return res;
}
public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C){
assert( w.size() == v.size() && C >= 0 );
int n = w.size();
if( n == 0 || C == 0 )
return 0;
memo = vector<vector<int>>( n, vector<int>(C+1,-1));
return bestValue(w, v, n-1, C);
}
};
Решайте снизу вверх с помощью динамического программирования
Чтобы смоделировать его, каждое положение определяется двумя положениями
class Knapsack01{
public:
// 用 [0...index]的物品,填充容积为c的背包的最大价值
int knapsack01(const vector<int> &w, const vector<int> &v, int C){
assert( w.size() == v.size() && C >= 0 );
if ( n == 0) {
return 0;
}
int n = w.size();
vector<vector<int>> memo( n, vector<int>(C+1,0));
for ( int j = 0; j <= C; j++ ) {
memo[0][j] = ( j >= w[0] ? v[0] : 0 );
}
for ( int i = 1; i < n; i++ ) {
for ( int j = 0; j <= C; j++ ) {
// 0~i这些物品容积为j的背包获得的最大值
memo[i][j] = memo[i-1][j];
if( j >= w[i] ) {
memo[i][j] = max( memo[i][j], v[i] + memo[i-1][j-w[i]]);
}
}
}
return memo[n-1][C];
}
};
0-1 Оптимизация задачи о рюкзаке
анализировать
Временная сложность задачи о рюкзаке 0-1 выше: O(nC), пространственная сложность: O(nС).
Проанализируем уравнение перехода состояний: F(i,C) = max{F(i-1, C), v(i) + F(i-1, C-w(i))}
i-й элемент строки зависит только от i-1 элемента строки. Теоретически необходимо сохранить только два ряда элементов. Пространственная сложность: O(2*C)=O(C).
Используйте два ряда по очереди, чтобы решить задачу о рюкзаке.
class Knapsack01{
public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C){
assert( w.size() == v.size() && C >= 0 );
int n = w.size();
if( n == 0 && C == 0 )
return 0;
vector<vector<int>> memo( 2, vector<int>(C+1,0));
for( int j = 0 ; j <= C ; j ++ )
memo[0][j] = ( j >= w[0] ? v[0] : 0 );
for( int i = 1 ; i < n ; i ++ )
for( int j = 0 ; j <= C ; j ++ ){
memo[i%2][j] = memo[(i-1)%2][j];
if( j >= w[i] )
memo[i%2][j] = max( memo[i%2][j], v[i] + memo[(i-1)%2][j-w[i]]);
}
return memo[(n-1)%2][C];
}
};
продолжать оптимизировать
Завершите задачу о рюкзаке всего одной строкой, что сложнее: обновляем содержимое справа налево.
Код
class Knapsack01{
public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C){
assert( w.size() == v.size() && C >= 0 );
int n = w.size();
if( n == 0 || C == 0 )
return 0;
vector<int> memo(C+1,0);
for( int j = 0 ; j <= C ; j ++ )
memo[j] = ( j >= w[0] ? v[0] : 0 );
for( int i = 1 ; i < n ; i ++ )
for( int j = C ; j >= w[i] ; j -- )
memo[j] = max( memo[j], v[i] + memo[j-w[i]]);
return memo[C];
}
};
Варианты задачи о рюкзаке 0-1
- Задача о нескольких рюкзаках: у каждого предмета больше 1, всего num(i)
- Полная проблема с рюкзаком: каждый предмет можно использовать бесконечно
- Многомерная стоимостная задача о рюкзаке: рассмотрим два измерения: объем и вес предмета.
- Добавьте больше ограничений между элементами: элементы могут быть взаимоисключающими, они также могут зависеть друг от друга.
0-1 Рюкзак Вопросы в интервью
leetcode 416. Разделить на равное и подмножество
анализировать
Типичная задача о рюкзаке: выберите определенный предмет из n предметов и заполните рюкзак суммой/2.
поиск памяти
class Solution {
private:
// memo[i][c] 表示使用索引为[0...i]的这些元素,是否可以完全填充一个容量为c的背包
// -1 表示为未计算; 0 表示不可以填充; 1 表示可以填充
vector<vector<int>> memo;
// 使用nums[0...index], 是否可以完全填充一个容量为sum的背包
bool tryPartition(const vector<int> &nums, int index, int sum){
if( sum == 0 ) {
return true;
}
if( sum < 0 || index < 0 ) {
return false;
}
if( memo[index][sum] != -1 ) {
return memo[index][sum] == 1;
}
memo[index][sum] = (tryPartition(nums, index-1 , sum ) ||
tryPartition(nums, index-1 , sum - nums[index] ) ) ? 1 : 0;
return memo[index][sum] == 1;
}
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for( int i = 0 ; i < nums.size() ; i ++ ){
assert( nums[i] > 0 );
sum += nums[i];
}
if( sum%2 ) {
return false;
}
memo = vector<vector<int>>(nums.size(), vector<int>(sum/2+1,-1));
return tryPartition(nums, nums.size()-1 , sum/2 );
}
};
Восходящее с использованием динамического программирования
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for( int i = 0 ; i < nums.size() ; i ++ ){
assert( nums[i] > 0 );
sum += nums[i];
}
if( sum%2 ) {
return false;
}
int n = nums.size();
int C = sum / 2;
vector<bool> memo(C+1, false);
for ( int i = 0; i <= C; i++ ) {
memo[i] = ( nums[0] == i );
}
for ( int i = 1; i < n; i++ ) {
for ( int j = C; j >= nums[i]; j-- ) {
memo[j] = memo[j] || memo[ j - nums[i] ];
}
}
return memo[C];
}
};
аналогичная проблема
- leetcode 322
- leetcode 377
- leetcode 474
- leetcode 139
- leetcode 494
------------------------- Великолепная разделительная линия --------------------
Друзья, которые прочитали это, могут нажать «Нравится» / «Подписаться», ваша поддержка — самая большая поддержка для меня.
личный блогСтек томатной технологиииДомашняя страница Наггетс
Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт WeChat: Tomato Technology Stack.