動的計画アルゴリズムの紹介と関連する問題.
ダイナミックプランニング(dynamic programming DP)は広い話題であり、私たち自身のコンピュータにおいて重要な役割を果たしているほか、経済管理、生産スケジューリング、エンジニアリング技術、最適制御などの分野で広く応用されている.例えば、最短ルート、在庫管理、資源配分、設備更新、ソート、ロードなどの問題は、動的計画方法で他の方法で解くよりも便利です.しかし、最も重要なアルゴリズムの1つとして、このアルゴリズムをマスターして、後でいくつかの実際の問題を解決するだけではなくて、DP方法を通じて、モデリングして、プログラミングします.自分で問題を解決する考え方をよく鍛えることができます.だから、これからの勉强では、DPの方法でプログラミングをモデリングして実际の问题を解决することを一歩一歩高めていきます(PS:いわゆる笔记试験の面接で、试験官からの実际の応用问题に遭遇して、どのようにDPの方法を采用して所定の时间内に効果的にこれらの実际の问题を解决するか、后で仕事の生活の中で、DPという考え方を使うかもしれません).はい、本題に入ります.
履歴:(参照:http://www.cppblog.com/Fox/archive/2008/05/07/Dynamic_programming.html対応する英語原版ウィキペディア:http://en.wikipedia.org/wiki/Dynamic_programming)
数学とコンピュータ科学の分野では、動的計画は、反復サブ問題(overlapping subproblems、再帰的に乗算したい)に分解され、最適サブ構造(optimal substructure、最短パスアルゴリズム)を有する問題を解決するために使用され、動的計画は通常のアルゴリズムよりも時間がかかる.
前世紀40年代、Richard Bellmanは最も早く動的計画という概念を用いて、最適な決定解問題を探す解法過程を記述した.1953年、Richard Bellmanは動的計画を現代的な意義に与え、この分野はIEEEによってシステム分析とエンジニアリングに組み込まれた.Bellmanの寄与を記念して,動的に計画したコア方程式を最適化問題を再帰的に再確認するBelman方程式と命名した.
「ダイナミックプランニング」(dynamic programming)という言葉では、programmingは「コンピュータプログラミング」(computer programming)のprogrammingとは関連なく、「数学計画」(mathematical programming)から来ており、最適化とも呼ばれています.したがって、計画とは、生成アクティビティの最適化ポリシーを指します.例を挙げると、展覧会のスケジュールを組むことを計画と呼ぶことができます.この意味で、計画は実行可能なアクティビティ計画を見つけることを意味します.
时间の関系で直接参照リンクを与えました:DPアルゴリズムを详しく绍介します:(后で时间があって、読んでから、自分で総括します)http://www.ahhf45.com/info/Data_Structures_and_Algorithms/algorithm/technique/dynamic_programming/index.htm
関連問題:(コードは作者の所有で、宣言してください.相互参照学習)
バックパック問題:(0/1バックパック)
郵便局の質問:
最も大きなサブシーケンスの問題:
履歴:(参照:http://www.cppblog.com/Fox/archive/2008/05/07/Dynamic_programming.html対応する英語原版ウィキペディア:http://en.wikipedia.org/wiki/Dynamic_programming)
数学とコンピュータ科学の分野では、動的計画は、反復サブ問題(overlapping subproblems、再帰的に乗算したい)に分解され、最適サブ構造(optimal substructure、最短パスアルゴリズム)を有する問題を解決するために使用され、動的計画は通常のアルゴリズムよりも時間がかかる.
前世紀40年代、Richard Bellmanは最も早く動的計画という概念を用いて、最適な決定解問題を探す解法過程を記述した.1953年、Richard Bellmanは動的計画を現代的な意義に与え、この分野はIEEEによってシステム分析とエンジニアリングに組み込まれた.Bellmanの寄与を記念して,動的に計画したコア方程式を最適化問題を再帰的に再確認するBelman方程式と命名した.
「ダイナミックプランニング」(dynamic programming)という言葉では、programmingは「コンピュータプログラミング」(computer programming)のprogrammingとは関連なく、「数学計画」(mathematical programming)から来ており、最適化とも呼ばれています.したがって、計画とは、生成アクティビティの最適化ポリシーを指します.例を挙げると、展覧会のスケジュールを組むことを計画と呼ぶことができます.この意味で、計画は実行可能なアクティビティ計画を見つけることを意味します.
时间の関系で直接参照リンクを与えました:DPアルゴリズムを详しく绍介します:(后で时间があって、読んでから、自分で総括します)http://www.ahhf45.com/info/Data_Structures_and_Algorithms/algorithm/technique/dynamic_programming/index.htm
関連問題:(コードは作者の所有で、宣言してください.相互参照学習)
バックパック問題:(0/1バックパック)
/***************************************************************************
*@coder: wanda1416 @editor:weedge
*date:2011/6/28
*comment:
NP ， 。 。
， ， ， 。 。
（ ）。
:(0/1 )
N V 。 i c[i]， w[i]。 ， 。
:( )
， ： ， 。
： f[i][v] i v 。 (DP) ：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 。
，f[v]=max{f[v],f[v-c[i]]+w[i]} ， 。
：“ i v ” ， i （ ），
i-1 。 i ， “ i-1 v ”，
f[i-1][v]； i ， “ i-1 v-c[i] ”，
f [i-1][v-c[i]] i w[i]。
f[v] i ， v。 ， f[N] [V]，
f[N][0..V] 。 “ ” ， f[v-1]， f[N] [V] 。
， 。
:
O(N*V)， ， O(N)。
， i=1..N， f[i][0..V] 。
， f [0..V]， i f[v] f[i][v] ？
f[i][v] f[i-1][v] f [i-1][v-c[i]] ， f[v] （ i f[v] ）
f[v] f[v -c[i]] ？ ， v=V..0 f[v]，
f[v] f[v-c[i]] f[i-1][v-c[i]] 。 ：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
f[v]=max{f[v],f[v-c[i]]} f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，
f[v-c[i]] f[i-1][v-c[i]]。 v ，
f[i][v] f[i][v-c[i]] ， ， P02 ，
01 。
****************************************************************************************/
#include
using namespace std;
#define digui
#define MAXSIZE 1000
/****************************
：//BY wanda1416
A[i][v] v i ，
B[i][v] i ，
max(A[n][v], B[n][v])
********************************/
int A[MAXSIZE+1][MAXSIZE+1],B[MAXSIZE+1][MAXSIZE+1];
int c[MAXSIZE+1];// i
int w[MAXSIZE+1];// i
int F(int n,int v){
if(n==0) return 0;
if( !A[n][v] && v >= c[n])
A[n][v] = F(n-1,v-c[n]) +w[n];
if(!B[n][v])
B[n][v] = F(n-1,v);
return A[n][v]>B[n][v]?A[n][v]:B[n][v];
}
/* //BY */
int f[MAXSIZE + 1];//f[i][v]: i v
int main()
{
int N, V;
cin >> N >> V;
int i = 1;
for (; i <= N; ++i)
{
cin >> c[i] >> w[i];
}
memset(f, 0, sizeof(f));// f 0
//f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
for (i = 1; i <= N; ++i)
{
for (int v = V; v >= c[i]; --v) //c[i] bound, bound = max {V - sum c[i,...n], c[i]}
{
f[v] = (f[v] > f[v - c[i]] + w[i] ? f[v] : f[v - c[i]] + w[i]);
}
}
// i=N ， F[V]
cout << f[V] << '
';
#ifndef digui
cout< 郵便局の質問:
/****************************************************************************************************************
*@author: qin.yusen @editor:weedge
*@date: 2011/06/28
*@comment:
DP
( )：
12 ， 0、4、5、10、12、18、27、30、31、38、39、47.
12 3 ， ， 。
， IOI2000 （International Olympiad in Informatics） DP ，
， IOI200 POST OFFICE
， ：
V ， P ， ， 。
， 。
： V P，1<=V<=300，1<=P<=30，P<=V； V x1,x2,…xV，1<=xi<=10000。
： S；
。 ：
OK， DP， ，DP， ， ， ， ，
DP ， ， DP 。
， 。 ：
（ ， ……， ）
： N x[1]~x[n]， ， ， ？
： N=2k ，x[k] x[k+1] ， 。
N=2k+1 ，x[k+1] （ ，
N=2k-1 ，x[k] ）
。 ：（ ， 。）（n ，m ）
1.n ，1 ：
， 1 1 ，2 1 。
， ，3 1 ,
： n ， 1 。 （ ）。
2.n ，2 ：
：4 2 ？4 2 ， 1 3 ，
2 2 ， 3 4 ，3 ， ，4 2 ，
3 。
： n ，2 ：
n 2 ， 1 n-1 ，...， i 1 n-i 1 ，
...， n-1 1 ； n-1 。 ，n 2 ， n-1 。
3.n ，m ：
， n ，m ( cost(n,m)) ，
i m-1 ；
1 。 i (range) 【m-1，n-1】；
i 。
DP ， DP 。
Cost[n,m] = min{Cost[i,m-1]+D[i+1,n]}， i=m-1,m,…,n-1
Cost[n,m]： n m
D[i,j]： i j 1 。
D[i,j]=D[i,j-1]+x[j]-x[(i+j)/2] , ， ， ， 。
， ：Cost[n][m] Cost[n][m-1] ， 2 ， ：
Cost[n][2]: Cost[n][0] n 1 ； Cost[n][1] n 2 ,
。。。。。。。
Cost[n][m-1] n m-1 ； Cost[n][m] n m 。（ ）
POJ ， 。
http://poj.org/problem?id=1160
***********************************************************************************************************/
#include
#define MAX_N 310
using namespace std;
/* */
int main()
{
/*
char a[8]; // holds two 4-byte ints
// ：0xffffffff 0x00000000
memset(a,0,4*sizeof(char));
memset(a+4,0xff,4*sizeof(char));
a[0]=0x01;
a[1]=0xff;
a[2]=0xff;
a[3]=0xff;
cout<>v>>p;
//V の x 1,x 2,...xV,1<=xi<=10000をインクリメント に える.
for(i = 1; i <= v; i++)
cin>>x[i];
memset(D, 0, sizeof(D));// Dの は て0
/** まずD[i][j]:i の からj の の から1つの を んで から までの と を する.
の は、D[i,j]=D[i,j−1]+x[j]−x[(i+j)/2]により、 と を る。
cost[i][0]:iの の から1つの を して を する 、すなわち からこの までの と D[1][i].*/
for(i = 1; i <= v; i++)
{
for(j = i + 1; j <= v; j++)
D[i][j] = D[i][j - 1] + x[j] - x[int((i + j) / 2)];
// cost[range][p-1]は、 のp-1 がrangeの を もよくカバーできることを し、range は[p-1,v-1]である。
//cost[i][0]は のcost[i][1]に するが、ここではpの わりに2 を いて を った
//cout< 最も大きなサブシーケンスの問題:
/**************************************************
@date:2011/05/21
@author:weedge
@comment:
： ， ， ， ， 。
：
b[i]: i a[i] ,
b[i+1]=b[i]>0?b[i]+a[i+1]:a[i+1]
************************************/
#include
#include
int maxsum(int num[], int n)
{
int max_sum = num[0];
int max = num[0];
int i = 1;/*gcc*/
for(; i0)
{
max_sum += num[i];
}
else
{
max_sum = num[i];
}
if(max_sum>max)
{
max = max_sum;
}
}
return max;
}
int main()
{
/*test*/
int a[8] = {1,-2,3,10,-4,7,2,-5};
int max_sum = maxsum(a,8);
printf("the max sum of the numbers is %i",max_sum);
return 0;
}