动态规划____背包(有容量 物品无限制)

此类问题的重点是 "状态转移",比如当前背包容量为300,我可以拿10,拿20,拿30.

所以 在当前状态下 如果我拿10了,状态就转移到290(300-10);拿20了,状态就转移到280(300-20);拿30亦然.

而每一个状态的int值 记录了该状态的 最大/小 的目的值.

当然,状态的转移有一定的限制条件,只能转移到可以转移的状态.(比如当前背包容量20,就不能拿30的了)

状态的转移也有一定范围

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 100010
#define INF -1

int money, kind;
int value[MAX], needmoney[MAX];
int map[MAX];

int max(int a, int b)
{
    return a>b?a:b;
}

int dp(int cur)
{
    //printf("cur = %d
", cur);
    if(map[cur] != INF)
        return map[cur];
    else
    {
        map[cur] = 0; //此行很重要啊亲!!!!! 不过可以INF直接设置为0,即 memset(map, 0, sizeof(map));
                         初始化成INF(-1) 再不重新赋成0 结果200会变为199,根本原因是递归的最后一步返回了-1
        for(int i = 0; i < kind; i++)
        {
            if(cur >= needmoney[i])//状态转移的限制条件!
            {
                 map[cur] = max( map[cur], dp(cur-needmoney[i]) + value[i]);
            }
        }
        return map[cur];//注意不要吧return 写在循环中!!!!!!!!!!!!!!!!!!!
    }
    printf("wrong");//无关紧要 为了提示而已
    return 0;
}

int main()
{
    int N;
    //freopen("1.txt", "r", stdin);
    scanf("%d", &N);

    while(N--)
    {
        memset(map, INF, sizeof(map));
        scanf("%d%d", &money, &kind);
        //printf("%d %d
", money, kind);
        for(i = 0 ; i < kind; i++)
        {
            scanf("%d%d", &value[i], &needmoney[i]);
        //    printf("%d %d
", value[i], needmoney[i]);
        }
        printf("%d
", dp(money));
    }
    return 0;
}

HRBUST 1053http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1053