전언

N차 프라이도 좋지만'셀리아에서 1000엔이면 최대 칼로리를 얼마나 섭취할 수 있을까'가 유행이기 때문이다.

1000엔짜리 트집을 잡아봤어요.

우리는'셀리아에서 1000엔이면 최대 몇 kcal을 섭취할 수 있는지'를 양자퇴화계산(Wildqat)으로 해결했다.

SMT 구해기(Z3)로'세제리아에서는 1천엔이면 최대 몇 kcal까지 섭취할 수 있나요?'

정수 계획법으로'세제리아에서 1000엔이면 최대 kcal을 얼마나 섭취할 수 있는지'를 구해냈다.

마르코프 프랜차이즈 몬테카로로'셀리아에서 1000엔이면 최대 몇 칼로리를 섭취할 수 있나요?'

엑셀의 솔버로'세제리아에서 1천엔이면 최대 kcal을 얼마나 섭취할 수 있을까'를 풀어봤다.

[Excel] VLOOKUP 함수로만 천엔세리아가 섭취하는 칼로리의 최대치를 구하는 방법

TeX 언어로'세제리아에서 1000엔이면 최대 몇 kcal까지 섭취할 수 있나'계산~ TeX 언어로 동태계획법(DP)~

본래 취지는'수법 최적화/다양한 Solver의 재미를 시도하라'는 것이어야 하는데, 어차피 묘회인 만큼 심야 분위기도 내가 좋아하는 언어를 소개하게 한다. 내일이면 쑥스러워 사라질지도 모른다.
DP에서 풀 수 있다면 아마도 대화무자를 돌릴 수 있을 것이다. 무자라면'누구나 간단한 프로그래머'일 것이다. 읽으면 알 수 있는 코드로 DP가 써도 무엇을 할지 꼭 알 수 있기를 기대한다.

이른바 무자

일본어 프로그래밍 언어.v1을 사용합니다.
https://nadesi.com/top/

데이터 준비

@marusho_summers씨의 GiitHub에서 빌려왔습니다(감사합니다).
DB 다운로드.nako

データベースURLは『https://github.com/marushosummers/Saizeriya_1000yen/raw/master/sensai/saizeriya.db』
データベース保存先は母艦パス＆「saizeriya.db」
データベースURLをデータベース保存先へHTTPダウンロード
終わり

대화무자는 주요 형태를 모함이라고 하는데, 이는 해바라기 시절부터 시작된 습관이다.
따라서 모함 경로에서 스크립트 파일과 같은 경로를 지정할 수 있습니다.

불러오기 테스트

DB 읽기 테스트.nako

データベース保存先は母艦パス＆「saizeriya.db」
データベースはデータベース保存先をSQLITE3開く
「SJIS」にSQLITE3出力コード設定
データ＝データベースで「select * from menu」をSQLITE3実行してCSV取得

表示用グリッドとはグリッド
そのアイテムはデータ
そのレイアウトは全体

표준 SQLite3을 두드리고 3행으로 행렬을 시각화합니다.
진짜 대박이다.

전체 탐색

모처럼 전탐을 오다.
하지만 열심히 하면 반납하지 않기 때문에 모두 하지 않고 20개의 메뉴만 깎는다.
전탐색.nako

# 読み込み
データベース保存先は母艦パス＆「saizeriya.db」
データベースはデータベース保存先をSQLITE3開く
「SJIS」にSQLITE3出力コード設定
データ＝データベースで「select * from menu」をSQLITE3実行してCSV取得

# 見出し列の削除
データの0個目を配列削除

# ガチでやると終わらないのでデータを減らす (TT
20回、データの0を配列削除

# 値段とメニュー名とカロリーの抽出
メニュー名一覧はデータの1個目を表列取得
値段一覧はデータの4個目を表列取得
カロリー一覧はデータの5個目を表列取得

# 初期化
最終カロリー = -1
最終注文一覧 = 「」
最終値段 = 0円
メニュー数はメニュー名一覧の配列要素数

# 全探索
●考える（注目メニューまで注文一覧と値段でカロリーを）
    もし，注目メニュー＝メニュー数ならば
        # これ以上メニューはないので、
        # カロリーが最大の場合には出力する変数を書き換える
        もしカロリーが最終カロリー以上ならば
            最終カロリーはカロリー
            最終注文一覧は注文一覧
            最終値段は値段
        戻る

    # 注目要素を採用したときの値段
    採用時値段は値段＋値段一覧[注目メニュー]

    # 注目メニューを選ぶと値段オーバーするか
    もし、採用時値段が1000円以下ならば
        # 注目要素を選んでも値段がオーバーしないので
        # 注目要素は選ぶことを考える
        採用時カロリーはカロリー＋カロリー一覧[注目メニュー]
        採用時注文一覧は注文一覧＆改行＆メニュー名一覧[注目メニュー]
        注目メニュー+1まで採用時注文一覧と採用時値段で採用時カロリーを考える

    # 注目メニューは選ばないとき
    注目メニュー+1まで注文一覧と値段でカロリーを考える

# よーく考える
0まで空と0円で0を考える

# 出力
出力注文一覧は最終注文一覧の配列上下空行削除して『と』で配列結合
「最終カロリーは{最終カロリー}kcal
最終値段は{最終値段}円
最終注文一覧は{出力注文一覧}です」と言う

終わり

함수 정의는 "●"로 시작하며 매개변수 목록은 뒤에 배치됩니다.
대화무자는'조사'라는 개념이 있는데 매개 변수에 조사를 더해 건네주는 것이다. 조사는 키워드의 인수 역할을 하고 순서를 바꿔도 함수를 문제없이 두드린다.
여러 개의 조사를 같은 임시 매개 변수에 분배할 수도 있다. 예를 들어'안녕하세요'와'안녕하세요'는 같은 동작이다.
이외의 말, "말"과 "말"은 서로 다른 함수로, 전자는 무자가 내부에서 실시하는 정보상자이며, 여기서는 오른쪽 메뉴로 정보를 복제할 수 있어 편리하다.
"엔"을 함부로 무시하면 이해하기 쉽다(?)코드를 쓸 수 있도록 규정하다.
20초 정도면 답이 나오는데 20개의 메뉴를 지워버려서 이건 안 돼.

DP

DP(Dynamic Program)로 풀면 TeX는 생략됩니다.
다이와타코로 DP에 쓰면 초보자라도 쫓아다니기 쉬워 밤늦게 흥분해서 썼다.
DP.nako

# 読み込み
データベース保存先は母艦パス＆「saizeriya.db」
データベースはデータベース保存先をSQLITE3開く
「SJIS」にSQLITE3出力コード設定
データ＝データベースで「select * from menu」をSQLITE3実行してCSV取得

# 見出し列の削除
データの0個目を配列削除

# 値段とメニュー名とカロリーの抽出
メニュー名一覧はデータの1個目を表列取得
値段一覧はデータの4個目を表列取得
カロリー一覧はデータの5個目を表列取得

# 初期化
メニュー数はメニュー名一覧の配列要素数
最適選択時カロリー表[メニュー数][1000] = 0
最適選択時値段差表[メニュー数][1000] = 0

# それぞれのメニューについて、ある値段のときに注文すべきか考える
注目メニューで0からメニュー数-1まで繰り返す
    注目メニュー値段は値段一覧[注目メニュー]
    注目メニューカロリーはカロリー一覧[注目メニュー]
    次メニューは注目メニュー+1
    # 「ある値段」を順番に検討する
    値段で0円から1000円まで繰り返す
        # 注目メニューを選ばなかったときの値段は
        非採用時カロリーは最適選択時カロリー表[注目メニュー][値段]
        # 考えている値段が注目メニューの値段を超えているか検討
        もし、値段が注目メニュー値段以上ならば
            # 注目メニューを注文するのにお金を払うとして、その金額を払う直前での最適選択を考える
            採用時残金は値段-注目メニュー値段
            # そのメニューを選んだときの最適選択した場合でのカロリー
            採用時カロリーは最適選択時カロリー表[注目メニュー][採用時残金]+注目メニューカロリー

            # 結局そのメニューは選ぶべきだったのか
            もし、採用時カロリーが非採用時カロリー以下ならば
                最適選択時カロリー表[次メニュー][値段]は非採用時カロリー
                最適選択時値段差表[次メニュー][値段]は値段
            違えば
                最適選択時カロリー表[次メニュー][値段]は採用時カロリー
                最適選択時値段差表[次メニュー][値段]は採用時残金
        違えば # そもそも買えない
            最適選択時カロリー表[次メニュー][値段]は非採用時カロリー
            最適選択時値段差表[次メニュー][値段]は値段

最終カロリーは最適選択時カロリー表[メニュー数][1000円]

# 各メニューを注文したのかを確認
最終注文一覧は空
最終値段は0円
値段は1000円
注目メニューでメニュー数-1から0まで繰り返す
    次メニューは注目メニュー+1
    注目メニュー値段は値段一覧[注目メニュー]
    採用時残金は値段-注目メニュー値段
    もし、最適選択時値段差表[次メニュー][値段]が採用時残金ならば
        最終注文一覧にメニュー名一覧[注目メニュー]を配列追加
        最終値段は最終値段＋注目メニュー値段
    値段は最適選択時値段差表[次メニュー][値段]

# 出力
出力注文一覧は最終注文一覧を『と』で配列結合
「最終カロリーは{最終カロリー} kcal
最終値段は{最終値段}円
最終注文一覧は{出力注文一覧}です」と言う

終わり

Qita는 다와타코의 문법 하이라이터를 지원하지 않아 읽기 어려워 타코 편집기에서 열고 중요한 부분을 캡처한 사진을 붙인다.

선배들과 같은 대답을 받아 마음이 놓였다.

결론

DP는 대화무자로 쓰면 쉽게 알 수 있는 것이 아니라 C++로 쓰면 비교적 잘 알 수 있다.
하지만 대화무자는 편하니 사용해 보세요.