Demo entry 6636617

backpack

   

Submitted by anonymous on Aug 27, 2017 at 14:22
Language: C. Code size: 586 Bytes.

int backPackII(int m, vector<int> A, vector<int> V) {
	// write your code here
	
	int n = A.size();
	vector<vector<int>> dp( n+1, vector<int>( m+1 ) );
	for( int j=0; j<=m; j++ ){
		dp[0][j] = INT_MIN;
	}
	
	for( int i=0; i<=n; i++ ){
		dp[i][0] = 0;
	}
	
	for( int i=0; i<n; i++ ){
		for(int j=0; j<m; j++){
			
			dp[i+1][j+1] = dp[i][j+1];
			
			if( j+1 >= A[i] )
				dp[i+1][j+1] = max( dp[i+1][j+1], dp[i][j+1-A[i]]+V[i] );
		}
		
	}
	
	int maxValue = INT_MIN;
	for( int i=m; i>=0; i-- ){
		maxValue = max( maxValue, dp[n][i] );
	}
	return maxValue;
}

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).