C++ – 基础背包问题

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

输入输出格式

输入格式:

第一行有22个整数T(1 \le T \le 1000)T(1≤T≤1000)和M(1 \le M \le 100)M(1≤M≤100),用一个空格隔开,TT代表总共能够用来采药的时间,MM代表山洞里的草药的数目。 接下来的MM行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。

输出格式:

1个整数,表示在规定的时间内可以采到的草药的最大总价值。

样例

样例输入:

70 3

71 100

69 1

1 2

样例输出:

3

(ps;题目来源 洛谷 p1048)

题解

这是一道标准的背包问题,背包属于动态规划中较为常见的题型,其基本理念为在规定的 容量/总价/时间 的限定中尽可能寻求最大的收益。其递推公式大致为

*if(j>s[i].s) dp[i][j]=max(dp[i-1][j-s[i].s]+s[i].v,dp[i-1][j]) else dp[i][j]=dp[i-1][j];* (ps:s[i].s代表第i件物品所占空间,s[i].v代表其价值。dp[i][j]代表当背包大小为j时的最大总价。i代表当前正在判断是否装入背包的物品。故dp[n][m] 便是最大值。 ) 代码如下;(ps;本代码加入了输出被选入物品名单的部分。)

#include 
#include 
#include 
using namespace std;
struct node {
	int v, s;
};
node va[101];
int dp[103][1100];
int main() {
	int c, n;
	scanf("%d %d", &c, &n);
	int tem[n];
	for(int i = 1; i <= n; i++)
		scanf("%d %d", &va[i].s, &va[i].v);
	for(int i = 1; i <= n; i++)
		//初始化dp[i][j]便于之后比较。
		dp[i][0] = 0;
	for(int j = 0; j <= c; j++)
		dp[0][j] = 0;
	for(int i = 1; i <= n; i++) {
		//双重循环遍历每个位置。
		for(int j = 0; j <= c; j++) {
			if(va[i].s > j)
				//判断当前背包是否能装下第i件物品。
				dp[i][j] = dp[i - 1][j];
			else {
				if(dp[i - 1][j - va[i].s] + va[i].v > dp[i - 1][j])
					//对比装了物品前后的总价值取最大的。
					dp[i][j] = dp[i - 1][j - va[i].s] + va[i].v;
				else dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[n][c] << endl;
	//输出最大值。
	for(int i = 1; i <= n; i++) tem[i] = 0;
	int j = c;
	for(int i = n; i > 0; i--) {
		if(dp[i][j] > dp[i - 1][j]) {
			tem[i] = 1;
			j = j - va[i].s;
		}
	}
	for(int i = 1; i <= n; i++)
		if(tem[i] == 1) cout << i << ' ';
	return 0;
}
/*附样例输入
15 5
2 6
2 3
6 5
5 4
4 6*/
/*表格输出方便研究。
  0__1__2__3__4__5__6__7__8__9_10_11_12_13_14_15
0!0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0!
1!0  0  6  6  6  6  6  6  6  6  6  6  6  6  6  6!
2!0  0  6  6  9  9  9  9  9  9  9  9  9  9  9  9!
3!0  0  6  6  9  9  9  9 11 11 14 14 14 14 14 14!
4!0  0  6  6  9  9  9 10 11 13 14 14 14 15 15 18! 
5!0  6  6  9  9 12 12 15 15 15 16 17 19 20 20 20! */ 

发表回复