九度OJ 1532 棋盘寻宝扩展 -- 动态规划【背包问题】

题目地址：http://ac.jobdu.com/problem.php?pid=1532

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

输入：: 输入包含多个测试用例，每个测试用例共有9行，第一行是一个限制值limit<=1000，下面还有8行8列，第i行的第j列的数字代表了该处棋盘上的礼物的价值，每两个数之间用空格隔开。

输出：: 对于每组测试用例，请输出你能够获得不超过限制值limit的最大价值的礼物。若没有符合条件的线路则输出-1。

样例输入：

90

4 2 5 1 3 8 9 7

4 5 2 3 7 1 8 6

7 2 1 8 5 9 3 6

2 8 9 5 6 3 1 7

1 2 4 5 3 7 9 6

3 5 7 8 9 6 2 4

10 8 1 4 7 5 3 9

7 4 6 2 1 3 9 8

样例输出：

来源：: 微策略2012年校园招聘笔试题

#include <stdio.h>

int Max (int a, int b){

    return (a > b) ? a : b;

}

int MaxValue (int checker[9][9], int limit){

    if (checker[1][1] >= limit)

        return -1;

    int value[9][9][1010];

    int i;

    int j;

    int t;

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

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

            for (t=0; t<=limit; ++t)

                value[i][j][t] = 0;

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

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

            for (t=0; t<checker[i][j]; ++t)

                value[i][j][t] = 0;

            for (t=checker[i][j]; t<=limit; ++t){

                if (i == 1 && j == 1){

                    value[i][j][t] = checker[i][j];

                    continue;

                }

                if (value[i-1][j][t-checker[i][j]] == 0 && value[i][j-1][t-checker[i][j]] == 0)

                    value[i][j][t] = 0;

                else{

                    value[i][j][t] = Max (value[i-1][j][t-checker[i][j]], value[i][j-1][t-checker[i][j]])

                                    + checker[i][j];

                }

            }

        }

    }

    return (value[8][8][limit] != 0) ? value[8][8][limit] : -1;

}

int main(void){

    int limit;

    int checker[9][9];

    int i;

    int j;

    while (scanf ("%d", &limit) != EOF){

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

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

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

            }

        }

        printf ("%d\n", MaxValue (checker, limit));

    }

    return 0;

}

巴特西

九度OJ 1532 棋盘寻宝扩展 -- 动态规划【背包问题】

最新文章

热门文章