洛谷P1048 采药 题解

从题目中可以看出我们要帮辰辰采药，每株药都有它的时间（占用空间）以及这株药的价值，而且需要使采到的药价值最大。有了占用空间和价值和在输入中的背包容量，我们就可以看出这题应该使用01背包dp来做这一题。

二维数组

使用二维数组$dp[i][j]$表明放了前$i$株草药，可用时间不超过$j$时的最大总价值

六要素

• 决策:①不采此药;②采此药
• $i$（前$i$个物品）为阶段
• $dp[i]$（前$i$$株草药）$[j]$（背包容量为$j$）为状态，表明当前最大总价值
• $dp[0][0]$=0为初始值
• $dp[m]$（所有物品）$[t]$（最大容量）为目标值
• 状态转移方程

if(j<si[i])dp[i][j]=dp[i-1][j]/*不采药*/;//如果没有时间采药 那么就不采药
else dp[i][j]=max(dp[i-1][j]/*不采药*/,dp[i-1][j-ti[i]]+si[i]/*采药*/);//否则 就判断采药或不采药哪个价值更大

二维数组$Ac$ $Code$

#include <bits/stdc++.h>
#define MAX 1001
using namespace std;
int t,m,ti[105],si[105],dp[105][1005];//t:背包容量,m:物品数量,a:重量,ti:占用背包空间,si:价值,dp[i][j]:只有前i株草药，背包容量为j时的最优解
int main()
{
	//memset(dp,0,sizeof(dp));
	scanf("%d%d",&t,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&ti[i],&si[i]);
	}
	for(int i=1;i<=m;++i)//循环前i个物品
	{
		for(int j=0;j<=t;j++)//循环背包容量
		{
			if(j<ti[i])dp[i][j]=dp[i-1][j]/*不采药*/;
			else dvp[i][j]=max(dp[i-1][j]/*不采药*/,dp[i-1][j-ti[i]]+si[i]/*采药*/);
		}
	}
	printf("%d",dp[m][t]);
	return 0;
}

但是由于第一维在使用后就没用了，所以我们可以把第一维删除掉，再更改状态转移方程，还可以倒着循环来解决重复采同一种药的问题

一维数组

使用一维数组$f[i]$表示可用时间不超过$i$的最大总价值

六要素

• 决策:①不采此药;②采此药
• $i$(只有$i$时间)为阶段
• $f[i]$(只有$i$时间)为状态，表明当前最大总价值
• $f[0]$为初始值
• $f[m]$(最大容量)为目标值
• 状态转移方程

f[j]=max(f[j]/*不采药*/,f[j-ti[i]]+si[i]/*采药*/);

一维数组$Ac$ $Code$

#include <iostream>
#include <cstring>
#include <cmath>
#include <climits>
#define MAX 1001
using namespace std;
int t = 0, m = 0, ans = 0, si[MAX], ti[MAX],f[MAX];//t:背包容量,m:草药数量,a:重量,ti:占用背包空间,si:价值,dp[i]:只有i时间的最优解
int main()
{
	scanf("%d%d", &t,&m);
	for (int i = 1; i <= m; ++i)scanf("%d%d", &ti[i], &si[i]);
	for(int i=1;i<=m;++i)//循环前i个物品
	{
		for(int j=t;j>=0;--j)//循环背包容量
		{
			if(j>=ti[i])//确认可以采此药
			{
				f[j]=max(f[j]/*不采药*/,f[j-ti[i]]+si[i]/*采药*/);
			}
		}
	}
	printf("%d",f[t]);
	return 0;
}