Dynamic Programming | Set 6 (Min Cost Path) | GeeksforGeeks

Dynamic Programming | Set 6 (Min Cost Path) | GeeksforGeeks
Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0).
Optimal Substructure
minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]
recomputations of same subproblems can be avoided by constructing a temporary array tc[][] in bottom up manner.

int minCost(int cost[R][C], int m, int n)

{

     int i, j;

     int tc[R][C]; 

     tc[0][0] = cost[0][0];

     /* Initialize first column of total cost(tc) array */

     for (i = 1; i <= m; i++)

        tc[i][0] = tc[i-1][0] + cost[i][0];

     /* Initialize first row of tc array */

     for (j = 1; j <= n; j++)

        tc[0][j] = tc[0][j-1] + cost[0][j];

     /* Construct rest of the tc array */

     for (i = 1; i <= m; i++)

        for (j = 1; j <= n; j++)

            tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + cost[i][j];

     return tc[m][n];

}

http://www.acmerblog.com/jiudu-1529-2403.html
现在有一个8*8的棋盘，上面放着64个价值不等的礼物，每个小的棋盘上面放置一个礼物（礼物的价值大于0小于1000），一个人的初始位置在棋盘的左上角，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，结束位置在棋盘的右下角，请设计一个算法使其能够获得最大价值的礼物。

03	int main() {

04	while(~scanf("%d",&map[0][0])) {

05	for(j=1; j<8; j++) {

06	scanf("%d",&map[0][j]);

07	map[0][j] += map[0][j-1];

08

}

09	for(i=1; i<8; i++) {

10	scanf("%d",&map[i][0]);

11	map[i][0] += map[i-1][0];

12	for(j=1; j<8; j++) {

13	scanf("%d",&map[i][j]);

14	map[i][j] += (map[i][j-1] > map[i-1][j] ? map[i][j-1]:map[i-1][j]);

15

}

16

}

17	printf("%d\n",map[7][7]);

18

}

19

return 0;

20

}

http://www.acmerblog.com/jiudu-1532-2406.html
现在有一个8*8的棋盘，上面放着64个不同价值的礼物，每个小的棋盘上面放置一个礼物（礼物的价值大于0小于100），一个人初始位置在棋盘的左上角，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，结束位置在棋盘的右下角。从棋盘的左上角移动到右下角的时候的，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，但是拿到的所有的礼物的价值之和不大于一个限定值limit，请设计一个算法请实现，使其能够获得不超过限制值limit的最大价值的礼物。

1. 在棋盘问题的基础上加了一个限制, 礼物数不能超过 limit

2. 这个限制使得状态转移方程需要进行一下变形

3. dp[i][j][k] 表示 第 (i,j) 个格子上限制最大价值为 k 时能够获得的最大价值

dp[i][j][k] = max(dp[i][j-1][k-matrix[i][j]], dp[i-1][j][k-matrix[i][j]]) + matrix[i][j]

4. 初始化时需要设置为 负无穷, 表示没有线路能够在不超过 limit 的情况下得到 (i,j)

int main( )

{

    int limit;

    while ( cin >> limit )

    {

        for (int i=0; i<8; i++)

            for (int j=0; j<8; j++)

                cin >> a[i][j];

  

        memset(dp, 0, sizeof(dp));

        if (a[0][0] <= limit)dp[0][0][a[0][0]] = 1;

        for (int i=0; i<9; i++)

            for (int j=0; j<9; j++)

            {

                if (j > 0)

                {

                    for (int k=limit; k>=a[i][j]; k--)

                    {

                        dp[i][j][k] |= dp[i][j-1][k-a[i][j]];

                    }

                }

                if (i > 0)

                {

                    for (int k=limit; k>=a[i][j]; k--)

                    {

                        dp[i][j][k] |= dp[i-1][j][k-a[i][j]];

                    }

                }

            }

  

        int res = -1;

        for (int i=limit; i>=0; i--)

        {

            if (dp[7][7][i])

            {

                res = i;

                break;

            }

        }

        cout << res << endl;

    }

  

    return 0;

}

http://blog.csdn.net/jackie_zhu/article/details/10416395
http://www.acmerblog.com/jiudu-1532-2406.html

02	int map[8][8], i, j, ans, limit;

03	void f(int x, int y, int sum) {

04	sum += map[x][y];

05	if (sum > limit)

06

return;

07	if (x == 7 && y == 7 && sum > ans)

08	ans = sum;

09	if (x < 7)

10	f(x + 1, y, sum);

11	if (y < 7)

12	f(x, y + 1, sum);

13

}

14	int main() {

15	while(~scanf("%d",&limit)) {

16

ans = 0;

17	for(i=0; i<8; i++) {

18	for(j=0; j<8; j++) {

19	scanf("%d",&map[i][j]);

20

}

21

}

22

f(0,0,0);

23	if(ans > 0)

24	printf("%d\n",ans);

25	else puts("-1");

26

}

27

return 0;

28

}

Read full article from Dynamic Programming | Set 6 (Min Cost Path) | GeeksforGeeks