采药 题解

(这篇题解可能和别的题解不同,一共有两个完整的AC代码)

解题思路

很典型的01背包问题
可以选择二维dp或者一维dp

二维dp思路:

1. 遍历每一个状态
2. 根据前一个状态，选择装或者不装之间的较大值
3. 取最末状态，最大容量为答案

AC代码

二维dp代码

执行用时 8ms
内存消耗 0.97MB

#include<cstdio>
#include<algorithm>
using namespace std;
int t[105], val[105];//采摘物品所需时间和物品对应价值 
int dp[105][1005];
int main() {
	int T, M;//t能花费的时间, m物品的数量 
	scanf("%d %d", &T, &M);
	for(int i = 1; i <= M; i++) {
		scanf("%d %d", &t[i], &val[i]);
	}
	
	for(int i = 1; i <= M; i++) {//从1开始遍历每一个物品，相当于状态的递增 
		for(int j = T; j >= 0; j--) {//
			if(j >= t[i]) {
				dp[i][j] = max(dp[i - 1][j - t[i]] + val[i], dp[i - 1][j]);
				//从上一个状态继承过来值（挪出空间装或者不装） 
			} else {
				dp[i][j] = dp[i - 1][j];
				//挪不出空间则直接继承 
			}
		}
	}
	
	printf("%d", dp[M][T]);//选取 第m个状态下 的 背包容量为t 的情况 
	return 0;
}

一维dp代码

执行用时 5ms
内存消耗 0.59MB

#include<cstdio>
#include<algorithm>
using namespace std;
int t[105], val[105];
int dp[1005];//不分状态，仅存放不同容量下的最大价值 
int main() {
	int T, M;//t能花费的时间, m物品的数量
	scanf("%d %d", &T, &M);
	for(int i = 1; i <= M; i++) {
		scanf("%d %d", &t[i], &val[i]);
	}
	for(int i = 1; i <= M; i++) {//遍历每一个物品 
		for(int j = T; j >= 0; j--) {//从大往小更新时间，避免重复更新 
			if(j >= t[i]) {//进行比较的条件为单独存放时可以放下该物品 
				dp[j] = max(dp[j - t[i]] + val[i], dp[j]);//选择原状态或挪出空间存放价值后的状态 
			}
		}
	}
	printf("%d", dp[T]);//选取最大容量下的价值 
	return 0;
}

欢迎加入团队
制作题解不易,跪求点赞!!!