リュックサックシリーズ第2編----01リュックサック(最大価値を解くときのリュックサックの品物)
1241 ワード
一:問題
01リュックサックの問題説明:容量Vのリュックサック.現在はN種類のものがあり、それぞれに1つのものしかなく、それぞれの物の体積はC 1,C 2,...,Cnであり、対応するそれぞれの価値はW 1,W 2,...,Wn.である.リュックサックの容量を超えない場合、荷物をリュックサックに入れる最大の価値は?
第1編の学習を経て、私達は最大の価値を解くことをマスターして、この編は最大の価値を求めると同時に、リュックサックの中にどんなものがあることを要求しますか?これは記録パスの問題です.
二:分析と理解
path[][2 D配列記録パスを設定します.
これは難しくありません.コードを見ると読めるはずです.
三:コード
四:データテスト
バックパックカタログに戻る--->バックパックカタログ
01リュックサックの問題説明:容量Vのリュックサック.現在はN種類のものがあり、それぞれに1つのものしかなく、それぞれの物の体積はC 1,C 2,...,Cnであり、対応するそれぞれの価値はW 1,W 2,...,Wn.である.リュックサックの容量を超えない場合、荷物をリュックサックに入れる最大の価値は?
第1編の学習を経て、私達は最大の価値を解くことをマスターして、この編は最大の価値を求めると同時に、リュックサックの中にどんなものがあることを要求しますか?これは記録パスの問題です.
二:分析と理解
path[][2 D配列記録パスを設定します.
これは難しくありません.コードを見ると読めるはずです.
三:コード
#include<iostream>
#include<algorithm>
using namespace std;
#define N 6
#define V 10 //
int w[N + 1] = { 0,2,3,1,4,6,5 }; //6 , 0
int v[N + 1] = { 0,5,6,5,1,19,7 }; //6 , 0
int dp[V + 5];
int path[N + 5][V + 5]; // 0
int main()
{
for (int i = 1; i <= N; i++)
{
for (int j = V; j >= v[i]; j--)
{
path[i][j] = 0;
if (dp[j] < dp[j - v[i]] + w[i])
{
dp[j] = dp[j - v[i]] + w[i];
path[i][j] = 1;
}
}
}
printf(" :%d
", dp[V]);
printf(" :");
int i = N;//N
int j = V;// V
while (i > 0 && j > 0)
{
if (path[i][j] == 1)
{
printf("%d ", w[i]);
j -= v[i];
}
i--;
}
printf("
");
return 0;
}
四:データテスト
バックパックカタログに戻る--->バックパックカタログ