I encountered this problem practicing for an upcoming national competition. The problem goes as follows: You need to create a mixture of two ingredients being in relation to 1:1. You are given N different mixtures, each having its own weight Wi, and its relation in the mixture between the ingredients Mi, Ti (Each value, N, Wi, Mi, and Ti, will be less than 100). We need to find the biggest possible weight of the final mixture, keeping the relation to 1:1. We can take from each given mixture how much we want, we don't necessarily need to take the whole mixture, we can take some portion of it.
So with the given relation 1:1 in the final mixture, we know that we need to have an equal amount of weight from both ingredients possible. After that I need to know if I take K grams of some mixture, how much weight that is for ingredients A and B. So I came up with the following formula:
Let W be the weight in grams, and M and T be the relation between the ingredients respectively. If we want to take K (K <= W) grams we have the following:
Weight of ingredient A = M * (K / (M+T))
Weight of ingredient B = T * (K / (M+T))
#include <bits/stdc++.h>
using namespace std;
class state{
public:
int weight;
int A;
int B;
};
int n;
vector<state> arr;
double ans= 0;
void f(double weight_A, double weight_B, int idx){
if(weight_A == weight_B)
ans = max(ans, weight_A + weight_B);
if(idx >= n)
return;
int weight = arr[idx].weight, relA = arr[idx].A, relB = arr[idx].B;
for(int K = 0; K <= weight; K++){
f(weight_A + relA * (K * 1.0/(relA + relB)), weight_B + relB * (K * 1.0/(relA + relB)), idx+1);
}
}
int main(){
cin>>n;
for(int i = 0; i < n; i++){
state in;
cin>>in.weight>>in.A>>in.B;
arr.push_back(in);
}
f(0.0, 0.0, 0);
cout<<fixed<<setprecision(8);
cout<<ans<<endl;
}
The problem I encountered was that we don't necessarily need to take integer weights, some times to achieve the maximum possible weight of the final product we need to take decimal weights. Let's take a look at this example:
5
14 3 2
4 1 3
4 2 2
6 6 1
10 4 3
We have N = 5, and in each row are given 3 integers, Wi, Mi, and Ti. The weight of the ith mixture and its relation. My solution for this example gives 20.0000, and the correct solution for the above example is 20.85714286. Looking back my initial idea won't work because of the decimal numbers. I suppose there is some formula but I can't figure it out, can anyone help?
