前言

前のブログでは01リュックサックについて話したばかりで、本章で述べる完全リュックサックと多重リュックサックと01リュックサックは同じ問題に属し、それらの3つの解決思想は数学モデルと同じで、唯一の違いは制約である.そのため、01リュックサックを見たことがない方は、まず01リュックサックを見てください.また、ここでは同じように2つのブログをお勧めします.完全リュックサック、多重リュックサックです.はい、次は本題に入ります.

完全リュックサック

シーン

私达は依然として01リュックサックのシーンを使って、すぐに私达はこの2つが実は同じ问题であることを発见します:同じ番组で、ゲストに1つのショッピングカートを出して、それからいくつかの商品を用意して、しかしすべての商品はもう1つではありませんて、无限で、1分の时间の内にゲストは自由にショッピングカートの中で任意の商品の数を詰めることができて、ショッピングカートの下で、それからショッピングカートの中の商品はゲストに属します同様に、ショッピングカートの商品の価値が最も大きいことを要求しています.これは完全なリュックサックの問題です.説明を容易にするために、数学の説明モデルを構築します.

数学モデル

変数Vを用いてショッピングカートの容量を記述する.Pを用いて選択した商品の総価値を説明する.次に、vi∈in∈{v 1,v 2,v 3,...,vn},(0<=i<=n),viがi番目の商品の体積を表すn個の要素を含む2つの集合を使用する.pi∈in∈{p 1,p 2,p 3,...,pn},(0<=i<=n),piはi番目の商品の価値を表す.最後に、i番目の商品の個数を変数xiで表し、xi>=0であることに注意します.私たちの目的はすべての商品の最大値を求めることです.すなわち、P=m a x(p 1 x 1+p 2 x 2+..+p i x i)P=max(p_1 x_1+p_2 x_2+…+p_ix_i)P=max(p 1 x 1+p 2 x 2+…+pixi)この結果は、V>=(v 1 x 1+v 2 x 2+v 2 x 2+...+v i x i)V>=(v_1 x_1+v_2 x_2+v_2 x_2+…+v_ix_i)V>=(v 1 x 1+v 2 x 2+v 2 x 2+vixi)と同様に、我々定義関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数を定義する.P=func(i,j)は、体積jにおける前のi種類の商品の組み合わせの最適解を表し、i=nの場合、j=Vの場合は結果が求められ,サブ問題の構築は同じであるが,まずi番目の商品のみを考慮し,このときxi>= 0であるため,P=m a x{f u n c(i−1,j−x i v i)+p i}(0<=x i v i<=j)P=max{func(i−1,j−x_iv_i)+p_i}(0<=x_iv_i<=j)P=max{func(i−1,j−xivi)+pi}( 0<=xivi

コード実装

class solution {
	vector<int> _p;	// 
	vector<int> _v;	// 
	int n;	// 
	int max_v;	// 
public:
	solution(const vector<int>& p, const vector<int>& v, int m) {
		_p = p;
		_v = v;
		n = _p.size() - 1;
		max_v = m;
	}

	int func() {
		vector<vector<int>> dp(n + 1, vector<int>(max_v + 1, 0));

		for (int i = 0; i <= n; i++)
			dp[i][0];
		for (int j = 0; j <= max_v; j++)
			dp[0][j];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= max_v; j++) {
				for (int k = 0; k * _v[i] <= j; k++)
					dp[i][j] = max(dp[i][j], dp[i - 1][j - k * _v[i]] + k * _p[i]);
			}
		}
		return dp[n][max_v];
	}
};

多重リュックサック

シーン

多重リュックサックも01リュックサックと同じで、完全リュックサックの特例で、私たちはまずこの番組を見に来ました.同じ番組で、ゲストにショッピングカートを送って、それからいくつかの商品を用意しましたが、商品ごとに1つではありません.無限ではありません.限られた数です.それは任意の非負の数である可能性があります.1分以内にゲストは勝手にショッピングカートに任意の商品を入れて制限を超えない数を積むことができます.カートの下に入れて、それからカートの中の商品はゲストに属して、同じように私达はカートの中の商品の価値が最も大きいことを要求して、これは多重リュックサックの问题で、ここまで私はみんなが自分でも独立してその数学の模型を书くことができると信じています.

数学モデル

変数Vを用いてショッピングカートの容量を記述する.Pを用いて選択した商品の総価値を説明する.ここでは,vi∈in∈{v 1,v 2,v 3,...,vn},(0<=i<=n),viはi番目の商品の体積を表すn個の要素を含む3つの集合を用いる.pi∈in∈{p 1,p 2,p 3,...,pn},(0<=i<=n),piはi番目の商品の価値を表す.ki∈in∈{k 1,k 2,k 3,...,kn},(0<=i<=n),kiはi番目の商品の個数を表す.最後に、i番目の商品の個数を変数xiで表し、このとき0<=xi<=kiであることに注意する.私たちの目的はすべての商品の最大値を求めることです.すなわち、P=m a x(p 1 x 1+p 2 x 2+..+p i x i)P=max(p_1 x_1+p_2 x_2+…+p_ix_i)P=max(p 1 x 1+p 2 x 2+…+pixi)この結果は、V>=(v 1 x 1+v 2 x 2+v 2 x 2+...+v i x i)V>=(v_1 x_1+v_2 x_2+v_2 x_2+…+v_ix_i)V>=(v 1 x 1+v 2 x 2+v 2 x 2+vixi)と同様に、我々定義関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数関数を定義する.P=func(i,j)は、体積jにおける前のi種類の商品の組み合わせの最適解を表し、i=nの場合、j=Vの場合は結果が求められるが,サブ問題の構築は同じであり,まずi番目の商品のみを考慮するので,P=m a x{f u n c(i−1,j−x i v i)+p i}(0<=x i v i<=j&x i<=j&x i<=k i)P=max{func(i−1,j−x_iv_i)+p_i}(0<=x_iv_i<=j&x_i<=j&x_i<=k_i)P=max{func(i−1,j−xivi)+pi}}(j=x_xivi)+pi}(0<=xi vi<=j&xi<=ki)このコードは自分で書くことをお勧めします.とても簡単です.完全にリュックの変形.

コード実装

class solution {
	vector<int> _p;	// 
	vector<int> _v;	// 
	vector<int> _k;
	int n;	// 
	int max_v;	// 
public:
	solution(const vector<int>& p, const vector<int>& v,const vector<int>& k, int m) {
		_p = p;
		_v = v;
		_k = k;
		n = _p.size() - 1;
		max_v = m;
	}

	int func() {
		vector<vector<int>> dp(n + 1, vector<int>(max_v + 1, 0));

		for (int i = 0; i <= n; i++)
			dp[i][0];
		for (int j = 0; j <= max_v; j++)
			dp[0][j];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= max_v; j++) {
				for (int k = 0; k <= _k[i] && k * _v[i] <= j; k++)
					dp[i][j] = max(dp[i][j], dp[i - 1][j - k * _v[i]] + k * _p[i]);
			}
		}
		return dp[n][max_v];
	}
};

ここで注意して、k<=k i k<=\_k_i k<=_kiはk∗に書くv [ i ] < = j k*\_v[i]<=j k∗_v[i]<=jの前に、そうでないと問題が発生します.はい、ここまで3つのリュックサックの問題は終わりました.実は私たちは完全なリュックサックをマスターすれば、実は他の2つのリュックサックの問題をマスターすることができます.最後に皆さんのお世辞に感謝します.間違いがあれば、皆さんが嫌がらない指摘をしてください.私は引き続き進歩して、もっと良い文章を見せます.