C++ program to solve Knapsavk Problem

// Knapsack Problem #include using namespace std; int main() { // Get number of items cout << "How many items? "; int N; cin >> N; // Get the maximum weight of knapsack cout << "What is the maximum weight of knapsack? "; int W; cin >> W; int profit[N+1]; int weight[N+1]; cout << "Enter profit & weights..." << endl; for (int i=1; i<=N; i++) { cout << "Item " << i << endl; cout << "Profit: "; cin >> profit[i]; cout << "Weight: "; cin >> weight[i]; cout << endl; } /* opt[n][w] = max profit of packing items 1..n with weight limit w */ /* sol[n][w] = does opt solution to pack items 1..n with weight limit w include item n? */ int opt[N+1][W+1]; bool sol[N+1][W+1]; for (int i=0; i<=N; i++) { for (int j=0; j<=W; j++) { opt[i][j] = 0; sol[i][j] = false; } } for (int i = 1; i <= N; i++) { for (int j = 1; j <= W; j++) { /* Don't take item n */ int option1 = opt[i-1][j]; /* Take item n */ int option2 = -21474836; // -2^31 if (weight[i] <= j) option2 = profit[i] + opt[i-1][j-weight[i]]; /* Select better of two options */ opt[i][j] = (option1 > option2) ? option1 : option2; sol[i][j] = (option2 > option1) ? true : false; } } /* Determine which items to take */ bool take[N+1]; for (int i = N, j = W; i > 0; i--) { if (sol[i][j]) { take[i] = true; j = j - weight[i]; } else { take[i] = false; } } /* Print results */ int totalProfit = 0; int totalWeight = 0; cout << endl; cout << "Item" << "\t" << "Profit" << "\t" << "Weight" << "\t" << "Take?" << endl; for (int i = 1; i <= N; i++) { cout << i << "\t" << profit[i] << "\t" << weight[i] << "\t" << take[i] << endl; if (take[i]) { totalProfit += profit[i]; totalWeight += weight[i]; } } cout << endl; cout << "Total Weight: " << totalWeight << endl; cout << "Total Profit: " << totalProfit << endl; return 0; } // aiuto