[C++知识库]洛谷 P1048采药 C语言

刚开始的思路：

刚开始就是贪心算法啊，算出每一种草药的性价比，先挑性价比高的草药采，再顺序采性价比第二高的，以此类推。最后代码写出来了，十个测试点全部阵亡，wrong answer。笑死，发现每种草药只有一个，贪心算不了，但是是标准的01背包动态规划问题。

正确的思路：

1. 对于M种草药，需要定义数组存储它们的相关信息。
2. 定义数组 time[] 存储每种草药采摘所需要的时间，定义数组 price[] 存储每种草药的价值。再定义一个二维数组value[i][j] 代表有 i 种元素，总时间为 j 的情况下的总价值。
3. 采用两个 for 循环，对于题目要求的 M,T，将 i=1 ~M，j=1 ~T 的所有 value[i][j] 计算出来，最后输出 value[M][T] 即可。
4. for 循环的解释：对于第 i 种草药，总时间为 j 的时候。如果 time[i]>j 说明采这种草药的时间是不够的，那么，value[i][j]=value[i-1][j] 。否则，就要考虑是采呢？还是不采呢？肯定要选总价值最大的那一种，于是，就存在一个比较， value[i][j]=max(value[i-1][j],value[i-1][j-time[i]]+price[i]) 。

c语言代码如下：

#include<stdio.h>
int max(int a,int b)//比较大小的函数
{
	if(a>b)
		return a;
	else
		return b;
}
int main()
{
	int T,M;
	int time[1001],price[1001];//两个存储相关信息的数组
	int value[1001][1001];//定义的二维数组，说明见上面文字部分
	scanf("%d %d",&T,&M);
	for(int i=1;i<=M;i++)
		scanf("%d %d",&time[i],&price[i]);
	for(int i=1;i<=M;i++)
	{
		for(int j=1;j<=T;j++)
		{
			if(time[i]>j)//如果第 i 种草药采摘的时间大于总时间 j，就采不了
				value[i][j]=value[i-1][j];
			else
				value[i][j]=max(value[i-1][j],value[i-1][j-time[i]]+price[i]);
				//如果可以采，就要用 max() 函数来判断是采的利益最大化还是不采的利益最大化
		}
	}
	printf("%d",value[M][T]);//直接输出 value[M][T]
}

自己简直是蒟蒻：

有一说一，第一次接触01背包问题，在CSDN上面看了好多文章和代码，对于两个 for 循环一直不是很理解，于是就去B站找了一些视频，要感谢某阿婆主（某阿婆主的视频）和另外一个阿婆（另外一个阿婆的视频）。同时还有另外一位CSDN的文章（这里就不放链接了，叉掉了找不到），还要感谢我在vae+发牢骚，给我小建议的程序员大佬和我们班的老温哈哈哈哈哈哈哈哈哈。想明白了感觉好简单，想不明白简直能把自己搞疯，一直想不明白的就是两个嵌套的 for 循环。其实就是把所有的情况随着每一次循环都计算出来，最后想输出什么就可以直接输出啊。恍然大悟的应该就是第一个阿婆视频中间部分的那个表格，看不懂代码的同仁可以去康康。