P1005-题解（C语言代码）01背包问题，代码不难，关键是思想

    今天通过这道题也终于学会了01背包问题，特此记录一下！

    

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

//获取最大值
int getMax(int x, int y) {
    if (x > y) {
        return x;
    } else {
        return y;
    }
}

int main() {

    //定义变量，输入数据
    int T = 0, M = 0;
    scanf("%d %d", &T, &M);
    int greedTime[M+1], greedValue[M+1];//注意数组的长度
    /*首个元素全部设为0，使得药草编号从1开始，
     * 也为了能够和下方的二维数组全部为0的第一行和第一列对应起来
     * */
    greedTime[0] = 0;
    greedValue[0] = 0;
    for (int i = 1; i < M+1; ++i) {
        scanf("%d %d", &greedTime[i], &greedValue[i]);
    }

    //创建著名的dp二维数组
    int dp[M+1][T+1];

    //初始化二维数组
    for (int i = 0; i <= M; ++i) {
        dp[i][0] = 0;//二维数组的第一列全部都是0
    }
    for (int i = 0; i <= T; ++i) {
        dp[0][i] = 0;//第一行也肯定都是0
    }

    
    //下面从第2行、第2列开始一行一行的填表
    for (int i = 1; i <= M; ++i) {
        for (int j = 1; j <= T; ++j) {
            if (greedTime[i] > j) {
                //如果总时间小于药草采摘的时间，那就不能采摘
                dp[i][j] = dp[i-1][j];
            } else {//寻找最优解
                dp[i][j] = getMax(dp[i-1][j], dp[i-1][j-greedTime[i]] + greedValue[i]);
            }
        }
    }

    //二维数组最右下角的元素数值就是最优解
    printf("%d\n", dp[M][T]);
    
    //下面这个二重循环打印了二维数组，如果你复制粘贴我的代码直接提交的话，记得删除下面这个二重循环
    for (int i = 0; i <= M; ++i) {
        for (int j = 0; j <= T; ++j) {
            printf("%2d ", dp[i][j]);
        }
        printf("\n");
    }
    return 0;
}