(備忘録)ナップサック問題を動的計画法で

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] << "です";
}

---

参考文献

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)