Hello all, I've been working on a dynamic programming problem, and I can't for the life of me find my bug. Any help would be much appreciated. I don't have the full problem statement, but basically you are given 0HAVE to use only 3 packages, and the total weight of the three packages must be <= 10. It's in C++
#include<iostream>
using namespace std;
int main()
{
//ifstream fin("in.txt");
//ofstream fout("out.txt");
//Set up
int dp[3][100]; //max value from 3 weights
int total;
cin >> total;
int w[total];
int v[total];
for (int i = 0; i < 3; i++)
for (int j = 0; j < 100; j++)
dp[i][j] = -1;
//Initialize table to 0, read input
dp[0][0] = 0;
for (int i = 0; i < total; i++)
cin >> w[i] >> v[i];
//DP table
for(int j = 1; j < total; j++)
{
for(int i = 3; i > 1; i--)
{
for (int k = 10; k > w[j]; k--)
{
if (dp[i-1][k-w[j]] != -1 && dp[i-1][k-w[j]] + v[j] > dp[i][k])
dp[i][k] = dp[i-1][k-w[j]] + v[j];
}
}
}
int best = -1;
int best_weight;
for (int i = 0; i < 10; i++)
{
if(dp[3][i] > best)
{
best = dp[3][i];
best_weight = i;
}
}
if (best != -1)
printf("%d %d\n", best_weight, best);
else
printf("Impossible.\n");
getchar();
getchar();
return 0;
}
