Algorithm for each element
Product A costs $ 10, B costs $ 3 and costs $ 0.50. The man bought 100 items for $ 100. How much of each product a person buys.
I found the answer as -
94 * 0.5 = 47
1 * 3 = 3
5 * 10 = 50
But I can't seem to implement it in Java like the solution I got from Hit and Trial. What will be the algorithm for solving this problem?
source to share
Normal brute force:
for (int i1 = 0; i1 <= 10; i1++) {
for (int i2 = 0; i2 < 34; i2++) {
int i3 = 100 - i2 - i1;
int total = i1 * 10 + i2 * 3 + i3 / 2;
if (total == 100 && i3 % 2 == 0)
System.out.println(i1 + " * 10 + " + i2
+ " * 3 + " + i3 + " * 0.5 = 100");
}
}
Gives two answers:
- 0 * 10 + 20 * 3 + 80 * 0.5 = 100
- 5 * 10 + 1 * 3 + 94 * 0.5 = 100
PS, of course, this is not an optimal solution, but only three elements and 100 total is a penalty (and optimal from a point in time required to encode it).
source to share
You need to implement your algorithm to solve these two equations
A + B + C = 100 -----------(1)
10A + 3B + 0.5C = 100 -----------(2)
From (2) you can find out that:
C = 100 - A - B
Substitute this information in (2)
10A + 3B + 0.5 * ( 100 - A - B) = 100
This reduces to
19A + 5B = 100
Then you can subtract that:
B = 20 - (19A/5)
Now try to figure out (using an int loop) for what the "integer" value A
will B
become an integer value (as usual in such problems, you always buy whole goods - like fruits there is no fraction)
You will find that when A = 5, B = 1.
Keep solving the equation this way and replace the variables A, B and C with Java and you should be able to get the solution.
source to share
Both solutions can be found very easily. the ring carrier has already given almost all the way to do this. ring media ends with:
B = 20 - (19A/5)
We know something else:
A, B, and C are all non-negative integer values.
This means 19A / 5 must be (1) an integer (otherwise B will not be an integer) and (2) at most 20 (otherwise B will be negative). This means that for (1) that A must be a multiple of 5, and for (2) A must be at most 5.
Also note that requirement 19A / 5 <= 20 can be rewritten as:
19A <= 100
For A, only two values are satisfied: 0 and 5. A very quick way to find all the solutions would then be to do something like:
for (A = 0; 19*A <= 100; A += 5)
{
// Show the solution for this value of A (with B = 20 - 19A/5 and C = 100 - A - B).
}
source to share
This is a variant of the knapsack problem , and you might be looking for dynamic programming that is better than brute force (in terms of computational complexity). A simple search gave links like this
source to share