Логика плана диеты, соответствующая наилучшему результату

Question

У меня следующая проблема. Я хочу составить план диеты, используя php & mysql. У меня есть следующее:

• Хлеб: 1 г белка, 2 г углеводов, 4 г жира
• Сахар: 3 г белка, 6 г углеводов, 1 г жира
• Кофе: 8 г белка, 2 г углеводов, 2 г жира
• Мясо: 7 г белка, 0 г углеводов, 12 г жира
• Молоко: 16 г белка, 12 г углеводов, 2 г жира

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

ЦЕЛЬ: 160 г белка - 41 г углевода - 120 г жира.

и покажите результат: 5 кусков мяса, 3 кусочка молока и т. Д.

У меня нет проблем с php и mysql. Я пытаюсь найти логику этой проблемы.

Answer 1

Не тривиально. Получить книгу или хорошую веб-страницу о Динамическое программирование , в частности Рюкзак проблема .

Answer 2

Вот решение грубой силы, которое должно работать. Это сценарий SQL (написанный на SQL Server, должен работать в MySql, но может потребовать незначительных изменений), который будет перебирать все возможные комбинации элементов, прежде чем найдет оптимальное решение.

-- Limits by protein/carb/fat
DECLARE @protein_limit INT
SET @protein_limit = 160

DECLARE @carb_limit INT
SET @carb_limit = 90

DECLARE @fat_limit INT
SET @fat_limit = 120



-- Table holding valid items
DECLARE @items TABLE
(
    id INT IDENTITY(1,1),
    name VARCHAR(50),
    protein INT,
    carb INT,
    fat INT
)

INSERT INTO @items
      SELECT 'Bread', 1, 2, 4
UNION SELECT 'Sugar', 3, 6, 1
UNION SELECT 'Coffee', 8, 2, 2
UNION SELECT 'Meat', 7, 0, 12
UNION SELECT 'Milk', 16, 12, 2


DECLARE @item_count INT
SELECT @item_count = COUNT(*)
FROM @items


-- From: /4415293/bitovye-tselochislennye-znacheniya-v-sql#4415326
DECLARE @bits TABLE
(
    number INT,
    [bit] INT,
    value INT
)


; with AllTheNumbers as (
    select cast (POWER(2, @item_count) as int) - 1 Number
    union all
    select Number - 1
    from AllTheNumbers
    where Number > 0
),
Bits as (
    select @item_count - 1 Bit
    union all
    select  Bit - 1
    from Bits
    where Bit > 0
)
INSERT INTO @bits (number, [bit], value)
select *, case when (Number & cast (POWER(2, Bit) as int)) != 0 then 1 else 0 end
from AllTheNumbers cross join Bits
order by Number, [Bit] desc


-- Table to hold trials - brute force!
DECLARE @trials TABLE
(
    trial_id INT,
    item_id INT,
    item_quantity INT
)


DECLARE @trial_max INT
SET @trial_max = (@protein_limit + @carb_limit + @fat_limit) * (POWER(2, @item_count))

DECLARE @trial_id INT
SET @trial_id = 1

DECLARE @base_quantity INT

WHILE @trial_id <= @trial_max
BEGIN

    SET @base_quantity = FLOOR((@trial_id / POWER(2, @item_count)))

    INSERT INTO @trials (trial_id, item_id, item_quantity)
    SELECT @trial_id + 1 + b.number
        , id
        , @base_quantity + b.value
    FROM @items a
    JOIN @bits b
        ON a.id = b.[bit] + 1



    --UPDATE @trials
    --SET item_quantity = @base_quantity + (@trial_id % item_id)
    --WHERE trial_id = @trial_id

    SET @trial_id = @trial_id + POWER(2, @item_count)

END


-- Get results of each trial
SELECT *
FROM @trials a
JOIN @items b
    ON a.item_id = b.id
ORDER BY a.trial_id

-- Use the trial_id field to reference the results of the previous select
SELECT *
FROM
(
    SELECT trial_id
        , SUM(protein * item_quantity) AS protein_total
        , SUM(carb * item_quantity) AS carb_total
        , SUM(fat * item_quantity) AS fat_total
    FROM @trials a
    JOIN @items b
        ON a.item_id = b.id
    GROUP BY trial_id
) a
WHERE protein_total <= @protein_limit
    AND carb_total <= @carb_limit
    AND fat_total <= @fat_limit
ORDER BY ((@protein_limit - protein_total) + (@carb_limit - carb_total) - (@fat_limit - fat_total)) ASC


-- This last query gets the best fit
SELECT c.name
    , b.item_quantity
FROM
(
    SELECT *
        , ROW_NUMBER() OVER (ORDER BY ((@protein_limit - protein_total) + (@carb_limit - carb_total) - (@fat_limit - fat_total)) ASC) AS rn
    FROM
    (
        SELECT trial_id
            , SUM(protein * item_quantity) AS protein_total
            , SUM(carb * item_quantity) AS carb_total
            , SUM(fat * item_quantity) AS fat_total
        FROM @trials a
        JOIN @items b
            ON a.item_id = b.id
        GROUP BY trial_id
    ) a
    WHERE protein_total <= @protein_limit
        AND carb_total <= @carb_limit
        AND fat_total <= @fat_limit
) a
JOIN @trials b
    ON a.trial_id = b.trial_id
JOIN @items c
    ON b.item_id = c.id
WHERE a.rn = 1

Это вернет три результата, каждый из которых будет иметь свой способ просмотра данных.

Дайте мне знать, если это работает!

Answer 3

Сама проблема немного ошибочна. Вы пытаетесь как можно ближе приблизиться к этим целям, не переходя? Вы просто ищете «какое-то решение», которое близко к этим цифрам? В зависимости от того, как вы определяете то, что квалифицируется как приемлемый ответ, это может быть очень простой или очень-очень трудной задачей, которую можно решить, не обращая внимания.

Например, добавьте новый ингредиент, содержащий 1 г каждого белка, углеводов и жиров. Также добавьте еще 3 ингредиента, каждый из которых содержит 1 г уникального питательного вещества - один - 1 г белка, 0 углеводов / жира, один - 1 г углеводов, 0 г белка / жира и т. Д. Здесь у вас есть как минимум два, если не много, решения, которые оба точно соответствуют цели.

Давайте продолжим и также предположим, что белковая пища для вас очень важна, так что вместо этого вы бы предпочли гораздо больше питательного вещества 1 г / 1 г / 1 г. Как мы взвешиваем решения, если мы не можем поразить цель, но вы не пьете 15 стаканов молока и ничего больше.

Проблема с рюкзаком - отличное начало, но есть миллион различных способов решения этой проблемы, и если вы собираетесь попытаться написать решение, я рекомендую попытаться решить что-то конкретное, а затем попытаться расширить его как Вы понимаете, что происходит под капотом.