Оптимизированное по пространству решение DP для задачи о ранце 0-1


Сложный уровень средний
Часто спрашивают в Амазонка BlackRock ByteDance CodeNation JP Morgan Netskope Ола Кабс Компания Qualcomm
Динамическое программирование ранец

Постановка задачи

Нам дают рюкзак, который может выдержать некоторый вес, нам нужно выбрать некоторые предметы из заданных предметов с некоторой ценностью. Вещи следует подбирать таким образом, чтобы ценность рюкзака (общая стоимость собранных предметов) была максимальной. Также нужно позаботиться о том, чтобы вес собранных вещей не превышал стоимость ранца. Здесь у нас может быть большой вес ранца. Мы не можем разделить предметы, то есть мы не можем взять половину предмета или одну треть. Таким образом, мы либо берем элемент, либо нет, дающий задаче название 0-1 Проблема с рюкзаком. Поскольку рюкзак может иметь большой вес, найдите оптимизированное по пространству решение DP для задачи о рюкзаке 0-1.

Пример

Оптимизированное по пространству решение DP для задачи о ранце 0-1

Number of Items = 3
Weight of Knapsack = 4
Weight of given items = {4, 5, 1}
Value of given items = {10, 20, 30}
30

Объяснение: мы выбираем последний элемент, потому что он дает лучший результат (или максимальное значение).

 

Number of Items = 5
Weight of Knapsack = 50
Weight of given items = {10, 10, 10, 10, 10}
Value of given items = {1, 2, 3, 4, 5}
15

Объяснение: Мы можем просто выбрать все предметы, так как вес нашего рюкзака равен общему весу всех предметов.

 

Подход для оптимизированного по пространству решения DP для задачи о рюкзаке 0-1

Как правило, мы решаем 0-1 Рюкзак с помощью динамическое программирование, Это один из стандартное динамическое программирование проблемы и многие другие стандартные задачи динамического программирования следуют той же схеме.

dp[i][j] = operation(dp[i-1][j], dp[i-1][j-wt[i] + val[i])

Here dp[i-1][j] represents we did not take the current item and

         dp[i-1][j-wt[i]] shows the reduced subproblem.

Под операцией я подразумеваю, что мы обычно либо максимизируем количество, либо минимизируем количество.

Единственная проблема, которая возникает при таком подходе, - это его квадратичная пространственная сложность. Обычно мы составляем массив dp или таблицу dp размеров: вес рюкзака x количество предметов. В случаях, когда у нас мало памяти. Мы можем дополнительно оптимизировать наши стандартные рюкзаки. Взглянув на рекурсивную формулу, мы поймем, что любое состояние в матрице dp зависит от ячейки, расположенной чуть выше или слева от нее. Затем мы можем просто сохранить две строки таблицы dp, первую текущую строку и вторую строку перед текущей строкой. Можно сказать, что проблема сводится к использованию этих двух строк. Мы можем решить это, если просто будем использовать вторую строку для нечетных строк индекса и первую строку для четных строк индекса.

Описанный здесь подход будет применим ко всем задачам, которые следуют одному и тому же шаблону, таким как сумма подмножества и т. Д.

Код:

C + + Код:

#include<bits/stdc++.h>
using namespace std;
int main()
 {
  int t;cin>>t;
  while(t--){
      int numberOfItems;cin>>numberOfItems;
      int weightOfKnapsack;cin>>weightOfKnapsack;
      int wt[numberOfItems],val[numberOfItems]; // store the weight and value of each item
      
      //Taking input
      for(int i=0;i<numberOfItems;i++)
          cin>>val[i];
      for(int i=0;i<numberOfItems;i++)
          cin>>wt[i];
     
      //dp array to store the max value which can be achieved at any weight
      int dp[2][weightOfKnapsack+1];
      
      memset(dp,0,sizeof dp); //initialising the dp array to 0
      
      for(int i=0;i<numberOfItems;i++){
          for(int j=0;j<=weightOfKnapsack;j++){
              dp[i&1][j] = max(dp[i&1][j], (i>=1 ? dp[(i-1)&1][j] : 0));
              if(j>=wt[i])
                  dp[i&1][j] = max(dp[i&1][j], (i>=1 ? dp[(i-1)&1][j-wt[i]] : 0)+val[i]);
          }
      }
      
      cout<<dp[(numberOfItems-1)&1][weightOfKnapsack]<<endl;
  }
}
2

3 // number of items

4 // weight knapsack can hold

10 20 30 // value of items

4 5 1 // weight of items

3

3

10 2 3

4 50 60
30 
0

Код Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
    	int t = sc.nextInt();
    	
    	while(t-- > 0){
    	    int numberOfItems = sc.nextInt();
    	    int weightOfKnapsack = sc.nextInt();
    	    
    	    // store the weight and value of each item
    	    int wt[] = new int[numberOfItems];
    	    int val[] = new int[numberOfItems]; 
    	    
    	    //Taking input
    	    for(int i=0;i<numberOfItems;i++)
    	        val[i] = sc.nextInt();
    	    for(int i=0;i<numberOfItems;i++)
    	        wt[i] = sc.nextInt();
    	   
    	    //dp array to store the max value which can be achieved at any weight
    	    int dp[][] = new int[2][weightOfKnapsack+1];
    	    
    	    //initialising the dp array to 0
    	    for(int i=0;i<2;i++) {
    	        for(int j=0;j<weightOfKnapsack+1;j++)
    	            dp[i][j] = 0;
    	    }
    	    
    	    for(int i=0;i<numberOfItems;i++){
    	        for(int j=0;j<=weightOfKnapsack;j++){
    	            dp[i&1][j] = Math.max(dp[i&1][j], (i>=1 ? dp[(i-1)&1][j] : 0));
    	            if(j>=wt[i])
    	                dp[i&1][j] = Math.max(dp[i&1][j], (i>=1 ? dp[(i-1)&1][j-wt[i]] : 0)+val[i]);
    	        }
    	    }
    	    
    	    System.out.println(dp[(numberOfItems-1)&1][weightOfKnapsack]);
    	}
    }
}

 

2

3 // number of items

4 // weight knapsack can hold

10 20 30 // value of items

4 5 1 // weight of items

3

3

10 2 3

4 50 60
30 
0

 

Анализ сложности

Сложность времени: O (N * W)

где N = количество элементов

W = весовой рюкзак может вместить

Если N = W, временная сложность = O (N ^ 2)

Космическая сложность: O (W)

где W = вес, который может вместить рюкзак, это уменьшенная пространственная сложность.