Алгоритм для каждого элемента

Question

Продукт A стоит 10 долларов США, B стоит 3 доллара США, а стоимость C стоит 0,50 доллара США. Человек купил 100 предметов за 100 долларов. Сколько из каждого товара покупал человек.

Я нашел ответ как-

94 * 0.5 = 47 
1 * 3 = 3  
5 * 10 = 50 

Но я не в состоянии выполнить его в Java, как решение, которое я получил результат от Hit и Trial. Каким будет алгоритм для решения этой задачи

Answer 1

Plain грубой силы:

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"); 

     } 
    } 

дает два ответа:

• 0 * 10 + 20 * 3 + 80 * 0,5 = 100
• 5 * 10 + 1 * 3 + 94 * 0,5 = 100

PS конечно, это не оптимальное решение, а всего три элемента и 100 суммарная сумма - это нормально (и оптимально с точки зрения времени, необходимого для его кодирования).

Answer 2

Это вариант knapsack problem, и вы можете найти решение на основе , которое должно быть лучше грубой силы (с точки зрения вычислительной сложности). Простой поиск дал ссылки, как this

Answer 3

Вы должны реализовать алгоритм для решения этих двух уравнений

A + B + C = 100 -----------(1) 
10A + 3B + 0.5C = 100 -----------(2) 

Из (2), мы можем выяснить, что:

C = 100 - A - B 

Substitue эта информация в (2)

10A + 3B + 0.5 * (100 - A - B) = 100 
This reduces to 
19A + 5B = 100 

Тогда вы можете вычесть это:

B = 20 - (19A/5) 

Теперь, попытайтесь выяснить (с помощью INT цикла), для чего «все» ценности A, будет B стать целым значением (как правило, в таких проблемах, вы всегда покупать целые товары -подобные плоды нет фракции)

Вы найдете, что при A = 5, B = 1.

Продолжайте решение уравнения таким образом и замените переменные A, B и C переменными Java, и вы сможете получить решение.

Answer 4

Оба решения можно найти очень легко. кольцевой носитель уже дал почти весь способ сделать это. кольцо на предъявителя закончилась:

B = 20 - (19A/5) 

Мы знаем, что-то еще, хотя:

A, B, and C are all non-negative integer values. 

Это означает, 19А/5 должен быть (1) целое число (иначе B не будет целое число), и (2) не более 20 (иначе B будет отрицательным). Это означает, что для (1) A должно быть кратным 5, а для (2) A должно быть не более 5.

отметить также, что требование 19A/5 < = 20 можно переписать в виде:

19A <= 100 

Есть только два значения А, удовлетворяют этому: 0 и 5. Очень быстрый способ найти все решения то должно было бы сделать что-то вроде:

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). 
}