C++入门算法1——dp(动态规划)

dp(动态规划)是十分重要的一个class="superseo">算法，一般来说这种算法会比dfs(深度优先搜索)快很多。

首先先来看一道例题 

题目链接：P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这是一道非常经典的dp例题。

记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这是我的提交记录。

好了，言归正传，

先讲一下二维 dp

二维dp比较简单，让我们定义状态 dp[i][j]是以 j 为容量为放入前i个物品(按 ii 从小到大的顺序)的最大价值，那么 i=1 的时候，放入的是物品 1，这时候肯定是最优的啦！

重点来了（敲黑板）状态转移方程：F[i,v]=max{F[i-1,v],F[i-1,v-c[i]]+w[i]}

接下来让我们看一下代码！

#include//万能头大法好！！！
using namespace std;
int w[105],val[105];
int dp[105][1005];
int main()
{
    int t,m,res=-1;
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&w[i],&val[i]);
    }
    for(int i=1;i<=m;i++) 
        for(int j=t;j>=0;j--)  
        {
            if(j>=w[i])
            {
                dp[i][j]=max(dp[i-1][j-w[i]]+val[i],dp[i-1][j]);
            }  
            else
            {
                dp[i][j]=dp[i-1][j];
            }              
        }
    printf("%d",dp[m][t]);
    return 0;
}

是不是非常的简单呢？

好，理解了二维dp如何做，现在让我们来思考一下它能不能继续优化呢？

不难发现，这道题可以用滚动数组进行优化（不知道滚动数组的小伙伴可以自行上网查找，我这里就不多赘述了）。

好了，让我们来看一下这道题的状态转移方程是什么。

重点来了（敲黑板）状态转移方程：F[v]=max{f[v],F[v-c[i]]+w[i]}

这样优化就完成了。

来看代码

#include
using namespace std;
int t,m;
int t1[105],price[105];
int dp[105][105];
int main()
{
	cin>>t>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>t1[i]>>price[i];
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=t;j>=0;j--)
		{
			if(j