(備忘録)ナップサック問題を動的計画法で
paizaでナップサック問題が解けなくてむかついたから勉強した備忘録
ナップサック問題とは
「あなたは冒険家で、最大で15キログラムの荷物を持って冒険に出発します。次のアイテムが提供されました。各アイテムの重さと価値は次の通りです。
マップ（Map） - 重さ: 2キログラム、価値: 10ゴールド
食料（Food） - 重さ: 5キログラム、価値: 7ゴールド
斧（Axe） - 重さ: 6キログラム、価値: 5ゴールド
ロープ（Rope） - 重さ: 1キログラム、価値: 2ゴールド
コンパス（Compass） - 重さ: 3キログラム、価値: 15ゴールド
あなたの目標は、持って行く荷物を選んで、ナップサックの容量内で最大の価値を得ることです。どのアイテムを選び、どのアイテムを選ばないかを決定してください。」
こんな問題
備忘録
テーブルのサイズは個数、重さの上限よりそれぞれ+1ずつ確保する。そうしないと動的計画法の部分で0個目を考えるときに場合分けしなくてはいけなくなる。メモリを節約するときはそっちのほうがいいかも？
dp.assign(num + 1, vector<int>(weightLimit + 1, 0));何個目まで考えるか。その個数以内で現在の重さでの最大の価値は？みたいな感じ
for (int fNum = 0; fNum < num; fNum++) { //何個目まで考えるか
for (int fWeight = 0; fWeight <= weightLimit; fWeight++) { //何グラムまで考えているか <=なの注意
//現在のを加える場合
if (fWeight - weight[fNum] >= 0) { //現在考えている重さ以下なら
dp[fNum + 1][fWeight] = max(dp[fNum + 1][fWeight], dp[fNum][fWeight - weight[fNum]] + value[fNum]);
}
//一個少ないのと比べる
dp[fNum + 1][fWeight] = max(dp[fNum][fWeight], dp[fNum + 1][fWeight]);
}
}作成したコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
//変数宣言
int num, weightLimit; //個数,重さの上限
vector<vector<int>>dp; //動的計画法テーブル 個数,重さ
vector<int>value; //価値の配列
vector<int>weight; //重さの配列
//初期化
cin >> num >> weightLimit;
dp.assign(num + 1, vector<int>(weightLimit + 1, 0)); //テーブルのサイズを変更して0で初期化 どっちも0の時の行列があるから+1 これをやらないとfNumが0の時例外処理が必要
value.assign(num, 0);
weight.assign(num, 0);
for (int e = 0; e < num; e++) {
cin >> weight[e] >> value[e];
}
//ナップサック問題を動的計画法で解く部分
for (int fNum = 0; fNum < num; fNum++) { //何個目まで考えるか
for (int fWeight = 0; fWeight <= weightLimit; fWeight++) { //何グラムまで考えているか <=なの注意
//現在のを加える場合
if (fWeight - weight[fNum] >= 0) { //現在考えている重さ以下なら
dp[fNum + 1][fWeight] = max(dp[fNum + 1][fWeight], dp[fNum][fWeight - weight[fNum]] + value[fNum]);
}
//一個少ないのと比べる
dp[fNum + 1][fWeight] = max(dp[fNum][fWeight], dp[fNum + 1][fWeight]);
}
}
cout << "価値の最高は" << dp[num][weightLimit-1] << "です";
}