DevJourney · code I wrote while learning
main.cpp
1.1 KB#include <iostream>
using namespace std;
int main()
{
int n, W;
if (!(cin >> n >> W))
return 0;
int wt[100], val[100];
// Read weights
for (int i = 0; i < n; i++)
cin >> wt[i];
// Read values
for (int i = 0; i < n; i++)
cin >> val[i];
int dp[101][101] = {0};
// Build DP table
for (int i = 1; i <= n; i++)
{
for (int w = 0; w <= W; w++)
{
dp[i][w] = dp[i - 1][w];
if (wt[i - 1] <= w)
{
int candidate = dp[i - 1][w - wt[i - 1]] + val[i - 1];
if (candidate > dp[i][w])
dp[i][w] = candidate;
}
}
}
cout << dp[n][W] << endl;
// Trace back selected items
int w = W;
int items[100];
int count = 0;
for (int i = n; i >= 1; i--)
{
if (dp[i][w] != dp[i - 1][w])
{
items[count++] = i - 1;
w -= wt[i - 1];
}
}
// Print items in correct order
for (int i = count - 1; i >= 0; i--)
cout << items[i] << " ";
cout << endl;
return 0;
}