Thursday, 6 April 2017

Geeksforgeeks Solution For " 0 - 1 Knapsack Problem "

GeeksforGeeks Solution For Hard Domain .Below You Can Find The Solution Of  School Basic ,Easy ,Medium . Or Hackerrank Solution You Can Also Direct Submit Your Solution to Geeksforgeeks Same Problem .You Need to login then you can submit you answers 

Problem :- 0 - 1 Knapsack Problem 

Submit Your Solution :- Click Here 

Solution :- 

#include<iostream>
using namespace std;
int max(int ,int ) ;
int Knapsack_Problem(int [],int [],int ,int ) ;
int main()
 {
 int t,no,w,val[100],weight[100],i ;
 cin>>t ;
 while(t--)
 {
     cin>>no ;
     cin>>w ;
    
     for(i=0;i<no;i++)
         cin>>val[i] ;
        
     for(i=0;i<no;i++)
         cin>>weight[i] ;
        
     no=Knapsack_Problem(val,weight,no,w) ;
     cout<<no<<endl ;
 }
 return 0;
}

int Knapsack_Problem(int val[],int weight[],int no,int w)
{
    int i,j ;
    int mat[no+1][w+1]={0} ;
   
    for(i=0;i<=no;i++)
        mat[i][0]=0 ;
       
    for(i=0;i<=w;i++)
        mat[0][i]=0 ;
   
    for(i=1;i<=no;i++)
    {
        for(j=1;j<=w;j++)
        {
            if(j>=weight[i-1])
            {
                mat[i][j]=max(mat[i-1][j],val[i-1]+mat[i-1][j-weight[i-1]]) ;
            }
            else if(i>1)
             mat[i][j]=mat[i-1][j] ;
        }
    }
    return mat[no][w] ;
}

int max(int a,int b)
{
 return a>b?a:b ;
}

Output:-



Geeksforgeeks Solution For " 0 - 1 Knapsack Problem "

No comments:
Write comments

Recommended Posts × +