正確な総括——01リュックサック問題(動的計画アルゴリズム)
4503 ワード
転自:原文:https://blog.csdn.net/xp731574722/article/details/70766804
今まで見た最も分かりやすい解釈は、一つもない.
————————————————————————————————————————————
0-1リュックサックの問題:n種類の物品と1つの容量がCのリュックサックが与えられ、物品iの重量はwiであり、その価値はviである.
問:リュックサックに入ったものをどのように選択すれば、リュックサックに入ったものの総価値が最大になるのでしょうか.
分析すると、すべてのものに直面して、私たちは2つの選択を持っていくか、持っていないかを選択するしかなく、あるものの一部を入れるか、同じものを何度も入れることはできません.
解決策:m[n][c]の大きさの2次元配列を宣言し、m[i][j]はi番目の物品に直面し、リュックサック容量がjの場合に得られる最大の価値を表し、m[i][j]の計算方法を簡単に分析することができる.
(1). jm[ i ][ j ] = m[ i-1 ][ j ]
(2). j>=w[i]の場合、リュックサックの容量はi番目のものを置くことができ、このものを持ってより大きな価値を得ることができるかどうかを考えなければなりません.
取り出すと、m[i][j]=m[i-1][j-w[i]+v[i]となります.ここでm[i-1][j-w[i]]とは、i-1アイテムを考慮したリュックサック容量がj-w[i]の場合の最大の価値であり、iアイテム目にw[i]を空けたスペースに相当する.
持たなければ、m[i][j]=m[i-1][j]、同(1)
持つか持たないかは、自然とこの2つの状況を比較してその価値が最も大きい.
これにより、状態遷移方程式を得ることができる.
if(j>=w[i]) m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]); else m[i][j]=m[i-1][j];
例:0-1リュックサックの問題.動的プランニングアルゴリズムを用いて0−1リュック問題を解く場合,2次元配列m[i][j]を用いてリュックの残容量j,オプションはi,i+1,......,n時0−1リュック問題の最適値を格納する.値配列v={8,10,6,3,7,2}を描画します.
重量配列w={4,6,2,2,5,1}
バックパック容量C=12の場合に対応するm[i][j]配列.
0 1 2 3 4 5 6 7 8 9 10 11 12 1 0 0 0 8 8 8 8 8 8 8 8 8 2 0 0 0 8 8 10 10 10 10 18 18 18 3 0 6 6 8 8 14 14 16 16 18 18 24 4 0 6 6 9 9 14 14 17 17 19 19 24 5 0 6 6 9 9 14 14 17 17 19 21 24 6 2 6 8 9 11 14 16 17 1919 21 24(1行目と1列目がシーケンス番号で、その数値は0)m[2][6]のように、2つ目の物品に直面してリュックサックの容量が6の場合、私たちは持たないことを選択することができ、それでは価値を得るのは1つ目の物品の価値8だけで、もし持っているならば、1つ目の物品を出して、2つ目の物品を置いて、価値10、私たちはもちろん持つことを選択します.m[2][6]=m[1][0]+10=0+10=10;順に類推してm[6][12]を得ることはすべてのものを考慮し,リュックサック容量がCの場合の最大価値である.
このステップでは、得られる可能性のある最大の価値を決定することができますが、どのようなものが最大の価値を得ることができるかは分かりません.
もう1つのx[]配列を起こし、x[i]=0は持たないことを表し、x[i]=1は持つことを表す.
m[n][c]が最適値であり、m[n][c]=m[n-1][c]であれば、n番目のものが同じであるか否かを示す場合、x[n]=0;そうでなければx[n]=1です.x[n]=0の場合、x[n-1][c]によって最適解が構築され続ける.x[n]=1の場合、x[n−1][c−w[i]]によって最適解の構築が継続される.このようにして,すべての最適解を構築することができる.△この全書アルゴリズムの本は、どう説明すればいいか分からない..
例:ある工場は来年A、B、C、Dの4つの新築プロジェクトがあると予想しているが、各プロジェクトの投資額Wkとその投資後の収益Vkは以下の表のように、投資総額は30万元で、どのようにプロジェクトを選んで総収益を最大にすることができるのか.
Project
Wk
Vk
A
15
12
B
10
8
C
12
9
D
8
5
前の2つのコードを結合
出力x[i]配列:0111、出力m[4][30]:22.
BCDを選択した3つのプロジェクトの総収益は最大で22万元だった.
しかし,このアルゴリズムは1つの最適解しか得られず,すべての最適解を得ることはできない.
今まで見た最も分かりやすい解釈は、一つもない.
————————————————————————————————————————————
0-1リュックサックの問題:n種類の物品と1つの容量がCのリュックサックが与えられ、物品iの重量はwiであり、その価値はviである.
問:リュックサックに入ったものをどのように選択すれば、リュックサックに入ったものの総価値が最大になるのでしょうか.
分析すると、すべてのものに直面して、私たちは2つの選択を持っていくか、持っていないかを選択するしかなく、あるものの一部を入れるか、同じものを何度も入れることはできません.
解決策:m[n][c]の大きさの2次元配列を宣言し、m[i][j]はi番目の物品に直面し、リュックサック容量がjの場合に得られる最大の価値を表し、m[i][j]の計算方法を簡単に分析することができる.
(1). j
(2). j>=w[i]の場合、リュックサックの容量はi番目のものを置くことができ、このものを持ってより大きな価値を得ることができるかどうかを考えなければなりません.
取り出すと、m[i][j]=m[i-1][j-w[i]+v[i]となります.ここでm[i-1][j-w[i]]とは、i-1アイテムを考慮したリュックサック容量がj-w[i]の場合の最大の価値であり、iアイテム目にw[i]を空けたスペースに相当する.
持たなければ、m[i][j]=m[i-1][j]、同(1)
持つか持たないかは、自然とこの2つの状況を比較してその価値が最も大きい.
これにより、状態遷移方程式を得ることができる.
if(j>=w[i]) m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]); else m[i][j]=m[i-1][j];
例:0-1リュックサックの問題.動的プランニングアルゴリズムを用いて0−1リュック問題を解く場合,2次元配列m[i][j]を用いてリュックの残容量j,オプションはi,i+1,......,n時0−1リュック問題の最適値を格納する.値配列v={8,10,6,3,7,2}を描画します.
重量配列w={4,6,2,2,5,1}
バックパック容量C=12の場合に対応するm[i][j]配列.
0 1 2 3 4 5 6 7 8 9 10 11 12 1 0 0 0 8 8 8 8 8 8 8 8 8 2 0 0 0 8 8 10 10 10 10 18 18 18 3 0 6 6 8 8 14 14 16 16 18 18 24 4 0 6 6 9 9 14 14 17 17 19 19 24 5 0 6 6 9 9 14 14 17 17 19 21 24 6 2 6 8 9 11 14 16 17 1919 21 24(1行目と1列目がシーケンス番号で、その数値は0)m[2][6]のように、2つ目の物品に直面してリュックサックの容量が6の場合、私たちは持たないことを選択することができ、それでは価値を得るのは1つ目の物品の価値8だけで、もし持っているならば、1つ目の物品を出して、2つ目の物品を置いて、価値10、私たちはもちろん持つことを選択します.m[2][6]=m[1][0]+10=0+10=10;順に類推してm[6][12]を得ることはすべてのものを考慮し,リュックサック容量がCの場合の最大価値である.
#include
#include
#include
using namespace std;
const int N=15;
int main()
{
int v[N]={0,8,10,6,3,7,2};
int w[N]={0,4,6,2,2,5,1};
int m[N][N];
int n=6,c=12;
memset(m,0,sizeof(m));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=c;j++)
{
if(j>=w[i])
m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
else
m[i][j]=m[i-1][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=c;j++)
{
cout< このステップでは、得られる可能性のある最大の価値を決定することができますが、どのようなものが最大の価値を得ることができるかは分かりません.
もう1つのx[]配列を起こし、x[i]=0は持たないことを表し、x[i]=1は持つことを表す.
m[n][c]が最適値であり、m[n][c]=m[n-1][c]であれば、n番目のものが同じであるか否かを示す場合、x[n]=0;そうでなければx[n]=1です.x[n]=0の場合、x[n-1][c]によって最適解が構築され続ける.x[n]=1の場合、x[n−1][c−w[i]]によって最適解の構築が継続される.このようにして,すべての最適解を構築することができる.△この全書アルゴリズムの本は、どう説明すればいいか分からない..
void traceback()
{
for(int i=n;i>1;i--)
{
if(m[i][c]==m[i-1][c])
x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
}
x[1]=(m[1][c]>0)?1:0;
}例:ある工場は来年A、B、C、Dの4つの新築プロジェクトがあると予想しているが、各プロジェクトの投資額Wkとその投資後の収益Vkは以下の表のように、投資総額は30万元で、どのようにプロジェクトを選んで総収益を最大にすることができるのか.
Project
Wk
Vk
A
15
12
B
10
8
C
12
9
D
8
5
前の2つのコードを結合
#include
#include
#include
using namespace std;
const int N=150;
int v[N]={0,12,8,9,5};
int w[N]={0,15,10,12,8};
int x[N];
int m[N][N];
int c=30;
int n=4;
void traceback()
{
for(int i=n;i>1;i--)
{
if(m[i][c]==m[i-1][c])
x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
}
x[1]=(m[1][c]>0)?1:0;
}
int main()
{
memset(m,0,sizeof(m));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=c;j++)
{
if(j>=w[i])
m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
else
m[i][j]=m[i-1][j];
}
}/*
for(int i=1;i<=6;i++)
{
for(int j=1;j<=c;j++)
{
cout< 出力x[i]配列:0111、出力m[4][30]:22.
BCDを選択した3つのプロジェクトの総収益は最大で22万元だった.
しかし,このアルゴリズムは1つの最適解しか得られず,すべての最適解を得ることはできない.