lantern

用户名：dotcpp0630548

访问量：2281

签　名：

等　　级
排　　名	247
经　　验	6054
参赛次数	8
文章发表	105
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

如有疑问，加QQ：2429936707

TA的其他文章

把数字转换成字符串，这样就好处理了
浏览：14

用结构体数组和qsort排序
浏览：8

可以在输入的时候同时统计最大最小值
浏览：8

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

这道题的本质就是01背包问题

　　作者: lantern　　　　发表时间：2024-08-16 20:27:33 浏览：55　|　评论：0　

原题链接：采药

太难理解了，特别是那个二维数组。我前几次都理解不了，好在01背包问题只要把实现部分的代码背下来也能用，我理解不了的时候就是背。
那么就用01背包问题来说，最难理解的那个二维数组很多人不知道那个i和j是什么意思
```
dp = [
    [0, 0, 0, 0, 0, 0], 没有物品时，所有容量下的最大价值为 0
        [0, 0, 0, 0, 0, 0], 只有物品 1
        [0, 0, 0, 0, 0, 0], 物品 1 和 2
        [0, 0, 0, 0, 0, 0]    所有物品
]

```
i表示第几件物品，而j表示我的背包在重量为j时，我的包里价值有多大（也就是我的包里有几件物品），这就是为什么dp数组的最后一个数就是最大值了。
而要实现“我的背包在重量为j时，我的包里价值有多大”这个问题，就用到了状态方程。
```c
if (j < t[i]) {
    dp[i][j] = dp[i - 1][j];
}
else {
    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i]] + m[i]);
}
```
```c
#include <stdio.h>
#define MAX 1001
#define max(a,b) (a>b?a:b)
int T, M;
int dp[MAX][MAX];
int fun(int* t, int* m) {
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= T; j++) {
            if (j < t[i]) {
                dp[i][j] = dp[i - 1][j];
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i]] + m[i]);
            }
        }
    }
    return dp[M][T];
}
int main() {
    scanf("%d %d", &T, &M);
    int t[MAX], m[MAX];
    for (int i = 1; i <= M; i++) {
        scanf("%d %d", &t[i], &m[i]);
    }
    printf("%d", fun(t, m));
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

lantern

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

汽水瓶（C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

不需要数组和指针的做法！！！

素数判断模板题(题解中的函数能用来判断大数是不是素数)

这道题的本质就是01背包问题

评论区

精彩推荐

C语言训练-邮票组合问题* （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

printf基础练习2 （C语言代码）

C二级辅导-计负均正（C语言代码）

数组输出（C语言代码）错误？？？

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

哥德巴赫曾猜测（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

lantern

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

汽水瓶 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

不需要数组和指针的做法！！！

素数判断模板题(题解中的函数能用来判断大数是不是素数)

这道题的本质就是01背包问题

评论区

精彩推荐

C语言训练-邮票组合问题* （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

数字整除 （C++代码）——(22行代码)真的只需要两个变量就够了

printf基础练习2 （C语言代码）

C二级辅导-计负均正 （C语言代码）

数组输出 （C语言代码）错误？？？

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

哥德巴赫曾猜测 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

汽水瓶（C语言代码）

　　评论区

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

C二级辅导-计负均正（C语言代码）

数组输出（C语言代码）错误？？？

哥德巴赫曾猜测（C语言代码）