czy123

## 典型背包问题
### 1.当药草可以随便取的时候（题目中不是）
不需要考虑药草个数问题
dp[i]:代表i内时间取得的药草之和最大值；
h[j].t:代表第j颗药草所花时间 v代表对应价值
i从小到大逐渐循环求出题目中所要求的时间t内的最大价值
j无所谓
则建立方程
dp[i]=max(dp[i],dp[i-h[j].t]+h[j].v);
eg:题目中70时间内价值和=1时间内价值和+1 或 69时间内价值和+2取其中最大值
### 2.当指定药草数量的时候（题目）
需要2维数组额外记录取到的第几个草药 药草标识i在最外层循环
dp[i][j]:考虑前i颗草药在所有时间段内的最大价值 一直迭代到考虑所有药草
则在时间j内，第i颗草药可以取可以不去取，取两种情况下的最大值
时间j仍是从小到大 药草标识i在最外层
dp[i][j] = max(dp[i-1][j],dp[i-1][j-h[i].t]+h[i].v);
滚动数组；
取第一个草药所有符合的时间加入第一个价值，
第i颗草药符合的时间加入价值且剩余时间能取得最大值也可以加入 计算最大值 
dp[j]=max(dp[j],dp[j-h[i].t]+h[i].v);
```cpp
#include<iostream>
#include<string.h>
using namespace std;
/* 	背包问题 
dp[i][j] = max(dp[i-1][j],dp[i-1][j-h.t]+h.v);
或滚动数组；
取第一个草药所有符合的时间加入第一个价值，
第i颗草药符合的时间加入价值且剩余时间能取得最大值也可以加入 计算最大值 
dp[j]=max(dp[j],dp[j-h[i].t]+h[i].v);
*/
struct herb{
	int t;
	int v;
};
int dp[1001];
int main(){
	int T,M;
	struct herb h[101];  
	cin>>T>>M;
	for(int i=1;i<=M;i++){
		cin>>h[i].t>>h[i].v;
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=M;i++){
		for(int j=T;j>=0;j--){
			if(j>=h[i].t){
				dp[j]=max(dp[j],dp[j-h[i].t]+h[i].v);
			}
		}
	}
	cout<<dp[T]<<endl;
} 
```

0.0分

0 人评分

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

czy123

TA的其他文章

你可能喜欢

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

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

A+B for Input-Output Practice (VII) （C++代码）

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

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

采药-题解(C++代码)

评论区

精彩推荐

钟神赛车（C语言代码）

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

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

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

上车人数（C语言代码）

用筛法求之N内的素数。（C语言代码）

字符串的输入输出处理（C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

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

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

czy123

TA的其他文章

你可能喜欢

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

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

A+B for Input-Output Practice (VII) （C++代码）

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

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

采药-题解(C++代码)

评论区

精彩推荐

钟神赛车 （C语言代码）

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

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

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

上车人数 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

字符串的输入输出处理 （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

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

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

　　评论区

钟神赛车（C语言代码）

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

上车人数（C语言代码）

用筛法求之N内的素数。（C语言代码）

字符串的输入输出处理（C语言代码）