Какой алгоритм проверки условия?

Question

[blanka]

Не получается продумать алгоритм проверки.

Суть. Допустим, есть 3 вида товаров (SKU-1, SKU-2, SKU-3).
Есть комбинации товаров, которые могут быть списаны:
1. Любые 2 вида товаров (SKU) (3шт). То есть, комбинации SKU-1 и SKU-2, SKU-1 и SKU-3, SKU-2 и SKU-3.
2. Товар SKU-2 (2шт).

Всего было доступно:

• SKU-1 - 5шт
  
• SKU-2 - 5шт
  
• SKU-3 - 0
  

Есть данные, что:
- по условию № 1 списано 2 раза.
- по условию № 2 списано 2 раза.

Задача: проверить, возможно ли было такое списание.

Так, если всего товаров было 10 (5+5+0), то списание по условию №1 (3шт) 2 раза = 3 * 2 = 6, а по условию №2 (2шт) 2 раза = 2 * 2 = 4. Тогда 6 + 4 = 5 + 5 + 0 истина, что не правильно, так как при соблюдении условий есть остаток SKU-1 - 3шт.

Условия (изображение):

Подскажите в какую сторону копать, а то как-то не соображу.
Спасибо!

Answer 1

[Therapyx]

Дак по первому условию может быть списанно любые 2 вида товаров в кол-ве 3 шт.
Если первое списание будет полностью из SKU1 и второе в размере двух единиц из SKU1 и одной из SKU2, то в SKU2 остается ровно 4 для двух списываний из 2го условия.
Или я видимо не так понял первое условие, но "Любые 2 вида товароров 3шт". Все таки должно подразумивать в себе и возможность комбинирования этих товаров, там ведь не указанно, что списание может быть любым, но все 3 штуки должны быть списанны именно из 1го SKU

Comments

[blanka]

Наверное, стоит уточнить, что "Любые 2 вида товаров 3шт" означает именно комбинацию "И" (SKU-1 И SKU-2, например)

[Therapyx]

blanka: если можно брать только 1 товар по 3, то 5%3 != 0. Изначально будет неверно в контексте именно этого примера)

[blanka]

Therapyx: Долбаюсь с этой задачей который день.
Но условие такое: минимум 2 вида товаров, общим количеством 3 шт. одной покупкой ИЛИ товар-2 в количестве 2 шт. одной покупкой.
Когда известно, что всего товаров было (5+5+0).

То есть перебор вариантов показывает, что можно сделать такие группы:
1. Только "минимум 2 вида товаров, общим количеством 3 шт. " - 3 раза, остаток 1.
2. Только "товар-2 в количестве 2 шт." - 2 раза, остаток 6.
3. "товар-2 в количестве 2 шт." - 1 раз И "минимум 2 вида товаров, общим количеством 3 шт. " - 2 раза, остаток 2.
4. "товар-2 в количестве 2 шт." - 2 раза И "минимум 2 вида товаров, общим количеством 3 шт. " - 1 раз, остаток 3.
Не могу закономерность уловить.

[Therapyx]

blanka: видимо я никак не пойму сути этого задания хД Но если что идет в плане доказательств с остатком, то можешь попробовать доказать вот этим методом, https://de.wikipedia.org/wiki/Kongruenz_(Zahlentheorie) только хоть убей не помню как это на русском хД Ибо математику учил в Германии)

Answer 2

[Андрей]

Формально у Вас недоопределенная (количество переменных больше чем количество уравнений) система целочисленных линейных уравнений, которую необходимо решить в неотрицательных целых числах:
x - кол-во списаний по правилу SKU-1+SKU-2
y - кол-во списаний по правилу SKU-2+SKU-3
z - кол-во списаний по правилу SKU-1+SKU-3
t - кол-во списаний по правилу SKU-2+SKU-2

SKU-1: 1*x + 0*y + 1*z + 0*t = 5
SKU-2: 1*x + 1*y + 0*z + 2*t = 5
SKU-3: 0*x + 1*y + 1*z + 0*t = 0

Готового алгоритма для общего случая не подскажу.
Из-за того, что система недоопределенная она может иметь несколько решений, и поиск одного из них обычно ведется каким-либо поиском с постепенной фиксацией значений переменных.

P.S. Не увидел абзац про условия (по 2 раза) - т.е. дополняем уравнениями:

x + y + z = 2
t = 2

и конкретно в Вашем случае система становится полностью определенной и не имеющей решения в неотрицательных числах (из-за того, что SKU-3 было 0, а значит y=0 и z=0). :-(

Comments

[blanka]

Может тогда можно как-то перебором с поиском максимальных значений и условий типа max(SKU-1, SKU-2, SKU-3) и последующими операциями?

[Андрей]

Сколько у Вас будет SKU и условий в реальной жизни ? Если всего 3, то правила выводятся достаточно легко из базовых соображений.