knapsack problems

[nims11]

i am facing problems while solving knapsack problems using C++. Help me out.
i tried googling for it and found a page regarding it but it solved it using greed algo. but its not 100% trustworthy to produce the optimal result.
also can anyone give me an idea of how to solve these questions by trying to have every combination or brute force...

[ps - this time in zonal computing olympiad, one of the two questions was knapsack type problem. i solved the other one but failed to solve the knapsack problem which lead to my failure to enter the 2nd round. exactly same thing happened with me last year too.
i am very sad coz this was my last chance(i m in 12th) to enter the national level informatics olympiad. also i failed to register for the zonal informatics olympiad(which is quite easy and majority selection takes place through it) due to lack of examination information.]