动态规划--数轴动态规划问题(算法,教程,动态规划,算法设计与分析,编程语言)

动态规划--数轴动态规划问题

导读：本文共2505字符，通常情况下阅读需要8分钟。同时您也可以点击右侧朗读，来听本文内容。按键盘←（左） →（右）方向键可以翻页。

摘要：01背包问题 1.如何用子问题表示 P[1…n , C]表示总问题 dp[ i ][ j ]表示P[ i…n，j ]的最大价值则总问题P[1…n , C] = max{ P[2…n , C - v1 ] , P[ 2…n , C] } 2. 优化子结构和重叠子问题 3. 递归表达式 dp[ i ][ j ] = max{ dp[ i + 1][ j - wi ] + vi , dp[ i + ... ...

音频解说

01背包问题

在这里插入图片描述
1.如何用子问题表示

P[1…n , C]表示总问题

dp[ i ][ j ]表示P[ i…n，j ]的最大价值

则总问题P[1…n , C] = max{ P[2…n , C - v1 ] , P[ 2…n , C] }
2. 优化子结构和重叠子问题
3. 递归表达式

dp[ i ][ j ] = max{ dp[ i + 1][ j - wi ] + vi , dp[ i + 1][ j ]}(选与不选)
递归终点：dp[ n ] [ j ] = vn (j > wn) ; dp[ n ][ j ] = 0(j < wn)

4.伪代码

For j=0 To min(wn-1 , C) Do dp[ n ][ j ] = 0;For j=wn To C Do dp[ n ][ j ] = vn;For i = n-1 To 2 For j = 0 To min(wi-1 , C) dp[i][j] = m[ i+1 ][ j ]; For j = wi To C dp[i][j] = max{ dp[ i + 1][ j - wi ] + vi , dp[ i + 1][ j ]}if C < w1 dp[ 1 ][ C ] = dp[ 2 ][ C ]Else dp[ 1 ][ C ] = max{ dp[ 2 ][ C - w1 ] + v1 , dp[ 2 ][ C ] }