TRANSPORTING CARGO V2
A particular vehicle has two compartments that store cargo. One on the left, and one on the right. The vehicle is being used to transport NN indivisible objects. The ii-th object weighs wiwi and occupies vivi volume. Both compartments have a maximum capacity VV. Neither compartment can contain items if the sum of their volumes exceeds VV. You have to place each object in either the left or the right compartment.
A difference in total weights in the two compartments ruins the balance of the vehicle. Place the objects in a manner such that the difference in the sum of weights of the two compartments is minimized. Output −1−1 if it is not possible to fit the objects in the two compartments.
Input
Two integers N,VN,V in that order.
NN lines follow. Two integers wi,viwi,vi on the (i+1)(i+1)-th line.
Constraints
1≤N≤301≤N≤30
1≤vi≤V≤2001≤vi≤V≤200
1≤∑wi≤5⋅1031≤∑wi≤5⋅103
Output
A single integer denoting the minimum possible difference of weight between the two compartments. Output −1−1 if it is not possible to fit the objects in the two compartments.
Example 1
Input
5 10
16 2
19 2
16 3
15 3
19 4
Output
9
int ans=INT_MAX;
void helper(int i,int v,vector<int>&wt,vector<int>&vol,int v1,int v2,int w1,int w2){
if(i==wt.size()){
ans=min(ans,abs(w1-w2));
return;
}
if(v1+vol[i]<=v){
helper(i+1,v,wt,vol,v1+vol[i],v2,w1+wt[i],w2);
}
if(v2+vol[i]<=v){
helper(i+1,v,wt,vol,v1,v2+vol[i],w1,w2+wt[i]);
}
if(ans==0)return;
}
void solve() {
int n,v;
cin>>n>>v;
vi weight(n),volume(n);
for (int i = 0; i < n; i++)
{
cin>>weight[i]>>volume[i];
}
helper(0,v,weight,volume,0,0,0,0);
if(ans==INT_MAX){
cout<<-1<<endl;
return;
}
cout<<ans<<endl;
}
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.