Problem link => http://www.spoj.com/problems/BACKPACK/
My solution :
#include <iostream>
#include <map>
#include <tuple>
using namespace std;
multimap<int,pair<int,int>>data; //to store attachments
int wt[61],val[61];//to store main goods
int solve(int n,int vol){
if(n<1||vol<0||wt[n]>vol)
return 0;
if(wt[n]==-1)
return solve(n-1,vol);
int w = wt[n], v = val[n];
int ret = solve(n-1,vol-w)+w*v;
auto range = data.equal_range(n); //check if there are any attachments
int coun = v*w,cw = w;
for(auto i=range.first;i!=range.second;i++){
int w1 = i->second.first,v1= i->second.second;
coun+=w1*v1;
cw += w1;
ret = max(ret,solve(n-1,vol-w-w1)+w*v+w1*v1); //take only this attachment
ret = max(ret,solve(n-1,vol-cw)+coun); //take this attachment along with previous one *there can be only 2 attachments at max*
}
return ret;
}
int main ()
{
int t;
cin>>t;
while(t--){
int vmax,n;
cin>>vmax>>n;
int a,b,c;
int sz = 1;
for(int i=1;i<=n;i++){
cin>>a>>b>>c;
if(c==0){ //treat this as a main good
wt[i] = a;
val[i]=b;
}else{ //treat this as an attachment
data.insert(make_pair(c,make_pair(a,b)));
wt[i] = -1; //this indicates that this index is an attachment
}
}
cout << solve(n,vmax) << endl;
}
}
So this is just a backtrack solution and I've not memoized it yet. But the problem is I'm getting "Wrong Answer" error on submitting this code. I have checked this code on various test cases and its working fine . So, waht's the error and how can I fix it ?