题目链接

[NOIP2005 普及组] 采药 - 洛谷https://www.luogu.com.cn/problem/P1048

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

题目分析

 典型的01背包问题，给出二维解法和一维状态压缩解法

代码实现 

//01背包二维数组
#include
using namespace std;
int T, M;
int tim[101], val[101];
int f[101][1001];
 
int main() {
	cin >> T >> M;//采药时间、采药数目
	for (int m = 1; m <= M; m++) cin >> tim[m] >> val[m];
	//01背包动态规划核心代码
	for (int m = 1; m <= M; m++) {//遍历采药数目
		for (int t = 1; t <= T; t++) {//遍历采药时间
			f[m][t] = f[m - 1][t];
			if(t >= tim[m]) f[m][t] = max(f[m][t], f[m - 1][t - tim[m]] + val[m]);
		}
	}
	cout << f[M][T] << endl;
	return 0;
}

//01背包状态压缩
#include
using namespace std;
int T, M;
int tim[101], val[101];
int g[1001];
 
int main() {
	cin >> T >> M;//采药时间、草药数目
	for (int m = 1; m <= M; m++) cin >> tim[m] >> val[m];
	//状态压缩核心代码
	for (int m = 1; m <= M; m++) {
		for (int t = T; t >= tim[m]; t--) {
			g[t] = max(g[t], g[t - tim[m]] + val[m]);
		}
	}
	cout << g[T] << endl;
    return 0;
}