洛谷p1048采药

lyt0707

题目描述

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

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

这题是一个简单基础的01背包问题，或者说是模板题，01背包主代码如下：

for(int i=1;i<=n;i++)
{
   for(int j=m;j>=1;j--)
   {
      if(j>=w)
      f[j]=max(f[i-1][j],f[i-1][j-w]+c);
       else
          f[j]=f[i-1][j];
    }
}

什么意思呢？是这样的：“将前i件物品放入容量为j的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为j的背包中”，价值为f[i-1][j]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为j-w的背包中”，此时能获得的最大价值就是f[i-1][j-c]（c为价值）再加上通过放入第i件物品获得的价值c。

如果知道了这些，此题难度是不是大大下降？好了，直接粘代码吧：

#include <cstdio>
#include <algorithm>
int f[1009][109];
int w[101],c[101];//数组开在外面
using namespace std;
int main()
{
        int t,m;
        int i,j;
        scanf("%d%d",&t,&m);
        for(i=1;i<=m;i++)
        {         
           scanf("%d%d",&w,&c);
        }
        for(i=1;i<=m;i++)//状态转移方程
        {
                for(j=t;j>=0;j--)//想一想，能不能写成for(j=0;j<=t;j++)呢
                {
                        if(j>=w)
                        {
                                f[j]=max(f[i-1][j],f[i-1][j-w]+c);
                        }
                        else
                        {
                                f[j]=f[i-1][j];
                        }
                }
        }
        printf("%d",f[m][t]);
        return 0;
}