A box of pre-cooked food contains N dishes and each dish has 2 properties, its Protein content and its Fat content. We need to select a non-empty subset of these N dishes such that the ratio of total Protein content to total Fat content in these selected subset of dishes is equal to a given target T.
Answer Yes if possible, No otherwise.
Constraints: 1<=N<=50 1<=T,Protein_i,Fat_i<=10
Eg1:
N=3,T=5
[[8,1],[1,1],[2,1]] where first index corresponds to protein content and second is fat content. Answer is "Yes" because selecting 1st and 3rd dish yields (8+2)/(1+1) = 5.
Eg2:
N=3,T=6
[[8,1],[1,1],[2,1]]. Answer is "No"
I don't think bitmask would work given that N can be upto 50. Any other solutions to this problem?
Auto comment: topic has been updated by rasalghul (previous revision, new revision, compare).
Try the following dynamic programming solution: —
dp[no_dishes][sum_protein][sum_fat]=0 or 1-is it possible to have a subset from firstno_disheswith fat content equal tosum_fatand total protein equal tosum_protein.The reccurence would bedp[no_dishes][sum_protein][sum_fat]=(dp[no_dishes-1][sum_protein-Protein_i][sum_fat-Fat_i] or dp[no_dishes-1][sum_protein][sum_fat]).This is caused by the fact that we can choose to take the current dish or not.Finally,check if there is anydp[N][sum_protein][sum_fat]==1 and sum_protein/sum_fat==T.The complexity isO(n^3*max_fat*max_protein)which I believe is good for these constraints.Here is the code of your problem using the similar idea of Bodo