ayushexel's blog

By ayushexel, history, 8 years ago, In English

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 ?

  • Vote: I like it
  • 0
  • Vote: I do not like it