educative.io

Educative

0/1 Knapsack Simple Solution As Per Course Pattern - Tabulation

int SolveKnapsackTabulation(const vector<int>& profits, const vector<int>& weights, int capacity) {
  if(capacity < 0 || profits.size() != weights.size()) return 0;
  int num_items = profits.size();
  vector<vector<int>> dp(num_items+1, vector<int>(capacity + 1, 0));

  for(int i = 0; i <= num_items; i++) {
    for(int j = 0; j <= capacity; j++) {
      if(i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if(weights[i-1] > j) {
        dp[i][j] = dp[i-1][j];
      } else {
        dp[i][j] = max(dp[i-1][j], profits[i-1] + dp[i-1][j - weights[i-1]]);
      }
    }
  }
  return dp[num_items][capacity];
}

Hi @Rupinder_Ghotra

Your code seems fine :slight_smile: