0-1 نيپسڪ مسئلو لاءِ هڪ خلائي سڌريل ڊي پي حل


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon ڪاروڪ ByteDance ڪوڊشن JP مارگن نيٽپسڪو اولا ڪئابس Qualcomm
متحرڪ پروگرامنگ ڌڪ

مسئلي جو بيان

اسان کي نيپشا ڏنو ويو آهي جيڪو ڪجهه وزن رکي سگهي ٿو ، اسان کي ڏنل شين مان ڪجهه شيون ڪجهه قيمت سان وٺڻ جي ضرورت آهي. شيون اهڙي طرح چونڊڻ گهرجن جيئن ته ڪپڙن جي قيمت (اچارن جي کل شين جو تعداد) وڌ کان وڌ ڪيو وڃي. اسان کي پڻ انهي ڳالهه جو خيال رکڻو پوندو ته چونڊيل شين جو وزن ڳلوءَ جي قيمت کان وڌيڪ نه هوندو. هتي ، اسان وٽ وڏو ٿلهو وزن رکي سگهندو آهي. اسان شيون تقسيم نٿا ڪري سگهون ، يعني اسان شيءَ يا اڌ حصو جو اڌ حصو ڪونه وٺي سگهنداسين. ان ڪري ، يا ته اسان ھڪ شيءِ ڏيون يا نه جيڪو مسئلو ڏئي ٿو 0-1 نالي جو مسئلو. ڇاڪاڻ ته ٿلهي کان وڏو وزن رکي سگھي ٿو ، 0-1 نيپسڪ مسئلي لاءِ خلائي بهتر ڊي پي جو حل ڳوليو.

مثال

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

وضاحت: اسان صرف سڀني شين کي چونڊي سگهون ٿا ڇاڪاڻ ته اسان جي ڇڪ وزن اسان سڀني شين جي ڪل وزن جي برابر آهي.

 

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.

آپريشن جي ذريعي منهنجو مطلب آهي ته اسان عام طور تي يا ته مقدار کي وڌ ۾ وڌ يا گهٽ مقدار کي گھٽائي سگهون ٿا.

صرف جيڪو مسئلو هن طريقي سان پيدا ٿئي ٿو ، اهو سندس چوڪنڊو خلائي پيچيدگي آهي. اسان عام طور تي ڊي پي آر ٺاهيو يا ڊي پي ٽيبل طول و عرض جو وزن نيپس x ايڪس شيون. انهن حالتن ۾ جتي اسان ياداشت تي گهٽ هوندا آهيون. اسان پنهنجي معياري ڇڪ حل کي وڌيڪ بهتر بڻائي سگهون ٿا. تجريدي فارمولا تي هڪ نظر وجهڻ اسان کي بصيرت ڏي ٿو ته ڊي پي ميٽرڪس ۾ ڪا به رياست پنهنجي مٿان يا انهي جي کاٻي پاسي تي ڀاڙڻ واري آهي. ان کان پوء اسان صرف ڊي جي ميز جي ٻن قطار رکي سگهون ٿا ، پهرين موجوده قطار ، ۽ ٻيو ، موجوده قطار کان پهرين قطار. اسان چئي سگھون ٿا ته مسئلو هاڻي انهن ٻن قطارن کي استعمال ڪندي ٻڏل آهي. اسان اهو ڪم ڪري سگھون ٿا جيڪڏهن اسان ٻئي قطار کي بي جوڙ انڊيڪس قطار ۽ پهرين قطار کي اڃا تائين انڊيڪس جي قطار لاءِ استعمال ڪيو ٿا.

هتي ٻڌايل قائداعظم لاڳو ٿيندو سڀني مسئلن تي جيڪي ساڳي نموني عمل ڪندا ، جهڙوڪ ذيلي سيٽ ، وغيره.

ڪوڊ

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

جاوا ڪوڊ

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

 

پيچيدگي تجزيي

وقت جي پيچيدگي: اي (ن * ڊ)

جتي N = شين جو تعداد

W = وزن وارو ٿلهو ٿي سگھي ٿو

جيڪڏهن N = W ، وقت جي پيچيدگي = O (N ^ 2)

خلائي پيچيدگي: اي (ڊ)

جتي W = وزن وارو ٿلهو ٿي سگھي ٿو ، اهو گهٽجي ويو خلائي پيچيدگي آهي.