1 / 4
Oct 2009

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;
}
  • created

    Oct '09
  • last reply

    Oct '09
  • 3

    replies

  • 235

    views

  • 3

    users

I haven't looked at your algorithm in detail, but I can see three things straight away:

a) You are accessing dp[i][k] where i=3, which is out of bounds.
b) You are looping from large values of i to small values of i, but you are referencing dp[i-1][..] in your formula - this is always going to be -1.
c) You are using dp[3][100], but the second index is always either k, or less than k, and k is at most 10.. are you mixing up value and weight somewhere?

I think you're right. I'll be honest and say I'm on really shaky ground here, I've done knapsack problems but the limit of 10 is throwing me off. Still not sure what's going on

Suggested Topics

Topic Category Replies Views Activity
Off-topic 2 301 Jun '24

Want to read more? Browse other topics in Off-topic or view latest topics.