Calculate possible balances in piggy-bank by weight

I have solved Piggy-Bank problem on SPOJ using dynamic programming.

The question asks you to get the minimum value that is possible with given weight (\$w\$) and one or more coins (\$n\$) with given value, \$value[j]\$ and weight, \$weight[j]\$.

I am using following recurrence relation (zero indexed) to solve the problem:

$$dp[i] = \min\left \{ val[j] + dp[i - weight[j]]\right \} \forall j \in \left [ 0..n-1 \right ] \& i - weight[j] \geq 0$$

where \$dp[i]\$ is the minimum monetary value in a piggy bank with weight \$i\$.

\$dp[w]\$ gives the minimum values possible with given coins for given weight.

But it seems like the question is more quickly solved using a knapsack approach. Can anyone kindly tell why so and why is my approach inefficient?

This code is giving correct answer for all the sample cases:

#include 
#include 
#include 
#include 
#include 
#include 
#define out(i) printf("%d",i)
#define out2(i,j) printf("%d %d",i,j)
#define nl printf("\n")
#define in(i) scanf("%d",&i)
#define in2(i,j) scanf("%d %d",&i,&j)
#define sn(i) scanf("%s",i)
#define inf 0x3f3f3f3f
using namespace std;
int val[500], weight[500], dp[10001],n;

int getAnswer(int w)
{
    if(dp[w] != inf) return dp[w];

    for(int i = 0; i = 0)
        dp[w] = min(dp[w],val[i] + getAnswer(w - weight[i]));
    }

    return dp[w];
}
int main()
{
    // your code goes here
    int t;
    in(t);

    while(t--)
    {
        int e,f,w,ans;
        in2(e,f);
        w = f - e;
        for(int i = 0; i <= w; i++)
            dp[i] = inf;
        in(n);
        dp[0] = 0;
        for(int i = 0; i < n; i++)
            in2(val[i], weight[i]);

        ans = getAnswer(w);
        if(ans != inf)
            printf("The minimum amount of money in the piggy-bank is %d.\n",ans);
        else
            printf("This is impossible.\n");
    }
    return 0;
}

Well, I don't have comments on the algorithm, but if you don't mind, I'd like to recommend a few improvements in the code. Just because it is a programming challenge, doesn't mean we shouldn't write good and clean code.

First major issue with the code is the excessive use of macro constants and function-like marcos. This is a deprecated practice in C++ since the language offers inline functions and typed constants. So all those shady 2-3 letter function-macros should really be actual functions.

Also, give them better names. It is pretty hard to tell just by looking at the code what a call to in() is. There's also an in2(), how's that different from in()? The only difference seems to be that the latter takes two parameters. Well, if you use functions, you don't need two names, since a single name can be overloaded.

#define inf 0x3f3f3f3f

What's the meaning of the constant (which should really be a const int)? It is not the largest value you can fit in a 32bit integer. So what's the story behind that? If you're not going to encode that info in the name, at least provide a comment with the reasons behind that choice. If you are just looking for a very large number, than perhaps use std::numeric_limits::max().

int val[500], weight[500], dp[10001],n;

No need to make these variables global if they can be declared in the program stack and be passed as functions parameters, though the arrays are big. So perhaps they should be std::vectors.

int main()
{
    // your code goes here

Yep, I'd guess so ;)

StackExchange Code Review Q#74384, answer score: 2