学食で赤・緑・黄の栄養素を最小金額で得る手法

三重大学バーチャルキャンパス

はじめに

こんにちは！ふくぶちょ～です。
早速ですが皆さんは、学食で食事をしたときに上手く栄養が取れなくて困ったことはありませんか？今回はそれを解決する手法を提案したいと思います。

3群点数法について

https://www.univcoop.or.jp/service/food/three.html
を見ると食品を3つのグループ(赤・緑・黄)に分けたものらしく、赤は肉、緑は野菜、黄色は炭水化物などが属しています。
男性だと一食で赤は$${2.7}$$、緑は$${1}$$、黄は$${5.5}$$くらい取るといいらしいです。

あり得る状態

それぞれの色について$${0.1}$$刻みで値が決められているようです(実際はさらに細かく決まっている可能性があります)。
これを考えると赤の摂取量としては$${0,0.1,0.2,\dots,2.7}$$の$${28}$$通りあります($${2.7}$$を超えたものはまとめて$${2.7}$$とみなします)。
同様に緑は$${11}$$通り、黄色は$${56}$$通りあります。
すると、全体で$${28\times 11 \times 56 =17248}$$通り。

動的計画法(Dynamic Programming)

対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法(Wikipediaから)。
ではこれを用いて計算をしてみましょう。
この問題は個数制限無しナップサック問題という問題に帰着可能です。
C++で書くと以下のようなコードになります。
これによって、必要な栄養素をとるために必要な最低金額を計算することができます。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const long long int INF=1000000;
const long long int Rmax=27;
const long long int Gmax=10;
const long long int Ymax=55;
long long int dp[Rmax+1][Gmax+1][Ymax+1];
long long int N;
 
int main() {
    //料理の数を入力
    cin>>N;
    vector<long long int>R(N),G(N),Y(N),Cost(N);
    for (long long int i = 0; i < N; i++)
    {
        //各栄養素と価格を入力
        cin>>R[i]>>G[i]>>Y[i]>>Cost[i];
    }
    for (long long int r = 0; r <= Rmax; r++)
    {
        for (long long int g = 0; g <= Gmax; g++)
        {
            for (long long int y = 0; y <= Ymax; y++)
            {
                //最初答えはとても大きい数に設定しておく
                dp[r][g][y]=INF;
            }
        }
    }
    //スタート地点の価格を0円
    dp[0][0][0]=0;

    for (long long int r = 0; r <= Rmax; r++)
    {
        for (long long int g = 0; g <= Gmax; g++)
        {
            for (long long int y = 0; y <= Ymax; y++)
            {
                for (long long int i = 0; i < N; i++)
                {
                    //i番目の料理を注文した時の処理
                    dp[min(r+R[i],Rmax)][min(g+G[i],Gmax)][min(y+Y[i],Ymax)]=min(dp[r][g][y]+Cost[i],dp[min(r+R[i],Rmax)][min(g+G[i],Gmax)][min(y+Y[i],Ymax)]);
                }
            }
        }
    }
    cout<<dp[Rmax][Gmax][Ymax]<<endl;
}

復元処理

上記のコードでは具体的にどの料理をどれだけ注文すればいいかがわかりません。
そのためDP配列から復元処理をして計算します。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const long long int INF=1000000;
const long long int Rmax=27;
const long long int Gmax=10;
const long long int Ymax=55;
long long int dp[Rmax+1][Gmax+1][Ymax+1];
long long int N;
 
int main() {
    //料理の数を入力
    cin>>N;
    vector<long long int>R(N),G(N),Y(N),Cost(N);
    for (long long int i = 0; i < N; i++)
    {
        //各栄養素と価格を入力
        cin>>R[i]>>G[i]>>Y[i]>>Cost[i];
    }
    for (long long int r = 0; r <= Rmax; r++)
    {
        for (long long int g = 0; g <= Gmax; g++)
        {
            for (long long int y = 0; y <= Ymax; y++)
            {
                //最初答えはとても大きい数に設定しておく
                dp[r][g][y]=INF;
            }
        }
    }
    //スタート地点の価格を0円
    dp[0][0][0]=0;

    for (long long int r = 0; r <= Rmax; r++)
    {
        for (long long int g = 0; g <= Gmax; g++)
        {
            for (long long int y = 0; y <= Ymax; y++)
            {
                for (long long int i = 0; i < N; i++)
                {
                    //i番目の料理を注文した時の処理
                    dp[min(r+R[i],Rmax)][min(g+G[i],Gmax)][min(y+Y[i],Ymax)]=min(dp[r][g][y]+Cost[i],dp[min(r+R[i],Rmax)][min(g+G[i],Gmax)][min(y+Y[i],Ymax)]);
                }
            }
        }
    }

    struct Nutrition
    {
        long long int r,g,y;
    };

    //購入個数記録用配列
    vector<long long int>cou(N,0);

    Nutrition now;
    now.r=Rmax;
    now.g=Gmax;
    now.y=Ymax;

    //後の計算のためにdp[r][g][y]=それぞれ栄養量r,g,y以上取るために必要な金額に変更
    for (long long int r = Rmax; r >= 0; r--)
    {
        for (long long int g = Gmax; g >= 0; g--)
        {
            for (long long int y = Ymax; y >= 0; y--)
            {
                dp[r][g][y]=min({dp[r][g][y],dp[min(r+1,Rmax)][g][y],dp[r][min(g+1,Gmax)][y],dp[r][g][min(y+1,Ymax)]});
            }
        }
    }
    //復元実行
    while(now.r!=0||now.g!=0||now.y!=0){
        for (long long int i = 0; i < N; i++)
        {
            if(dp[now.r][now.g][now.y]==dp[max(now.r-R[i],0LL)][max(now.g-G[i],0LL)][max(now.y-Y[i],0LL)]+Cost[i]){
                now.r=max(now.r-R[i],0LL);
                now.g=max(now.g-G[i],0LL);
                now.y=max(now.y-Y[i],0LL);
                cou[i]++;
                break;
            }
        }
    }
    
    //購入する料理
    cout<<"Price : "<<dp[Rmax][Gmax][Ymax]<<endl;
    for (long long int i = 0; i < N; i++)
    {
        cout<<"No."<<i+1<<" : "<<cou[i]<<endl;
    }
    
}

実際に計算してみる

https://gakushoku.coop/search/ のサイトから$${18}$$種類のメニューを取り出して計算してみました。

メニュー

  1. チキン照り焼きソース　　

  2. チキン塩だれ

  3. サバ塩焼き

  4. サバ味噌煮

  5. オクラの巣ごもりたまご

  6. 白身魚フライ

  7. パリパリ春巻き

  8. 薩摩ハーブ鶏のレバー煮

  9. ハッシュブラウン

  10. いももち

  11. きんぴらごぼう

  12. ひじき煮

  13. 半熟卵

  14. 冷奴

  15. 野菜生活100

  16. ライス小

  17. ライス中

  18. ライス大

赤×10・緑×10・黄×10・価格

28 1 4 308
27 1 6 308
27 0 0 198
14 0 3 198
10 2 2 132
2 0 26 110
2 1 32 132
6 0 4 88
0 5 10 88
1 2 15 88
0 3 3 66
4 1 3 66
10 0 0 66
7 0 0 66
0 4 0 66
0 0 28 66
0 0 43 99
0 0 57 132

結果

サバ塩焼き$${1}$$個、ハッシュブラウン$${2}$$個、ライス中$${1}$$個で合計$${473}$$円、栄養素は$${2.7,1.0,6.3}$$で確かに安く栄養をとれている(ハッシュブラウンが緑なのはあまり納得いかないけど)ことがわかります。

おわり

いろいろコードをいじって遊んでみてね！
間違っていたら教えてください。

この記事が気に入ったらサポートをしてみませんか？