Manchester- 采药（0 1背包）

解题思路：

这个问题贪心算法是无法求出最优解的，因为可能还会剩下时间，但是一个剩下的时间又不够采药；

所以这个题的原型就是01背包，动态规划求最优解；

下面先解释第一张图：（可采药时间为10，五种药A  B  C  D  E ）

假设有A，B，C，D，E，五种药，对应图中第三列，从（1）A开始，（1）代表第一种药A（这里为了好看上了编号）；

m/t  ： m就是药的编号（比如你输入了三种药）他们的编号就对应1,2,3  编号0表示没有药；   t为分配给你采药的时间分别从0到10，你会问t不是10吗，不是，你可以先这样理解，动态规划，就是把你有的时间从0开始，（这里时间为10），分成11中情况即：0到10，让你用；

再看第一列time[m]:表示采第m种药所要的时间；

再看第二列value[m]:表示第m种药的价值；

这两列就是你输入的M种药，对应的采药时间和价值；

看懂上面的后，最后来看m/t所对应的红色和蓝色的部分：这一部分我们用一个二维数组定义：sumvalue[m][t];这个的作用是用来存最大价值；你会问为什么用二维数组，先别急；这个问题不好解释；

接着看图m==0，代表着(0)no 那一行；t==0，对应着0下面的那一列；m==0这一行，和t==0这一列，对应的sumvalue[m][t]都为0，因为m==0，代表没药可采，价值肯定为0；t==0，可用来采药的时间为0，那价值也一定为0；所以在一定药把sumvalue[m][t]初始化为0；

明白了表的含义后，我么你就要知道表中sumvalue[m][t]（即蓝色部分，红色部分上面解释了：初始化）是怎么来的：用就是这个公式：sumvalue[ m ] [ t ]=max {  sumvalue[ m-1 ]  [ t-time[m] ]  +  value[ m ]   ，sumvalue[ m-1 ]  [ t ]  }  

公式中红色字体中，有个隐含条件：[ t-time[m] ]要大于等于0；应为t的时间用来采time[m]的时间的药，要够，否则采不了，采不了的话sumvalue[ m ] [ t ]这个格子的值就等于sumvalue[ m-1 ]  [ t ]格子的值；  能采的话，就是它俩取最大值；

最后sumvalue[ 5]  [ 10]=15就是最优解；

以上是方法;

到这里你必须要会填表中sumvalue[ m]  [ t ]部分（多天几遍后，你就找到规律了），否则下面的理论会感觉很空洞；

按照0 1背包，每一种药 m，有两种选择，1.采   2.不采 ，如果采的话那么价值sumvalue[ m]  [ t ]=sumvalue[ m-1 ]  [t-time[m] ]  +  value[ m ] （即 价值等于第m-1种药装入容量为t-time[m] 的时间中的价值加上第m个物品的价值value[ m ]）这句话只有用背包才说的清楚； 如果不采的话sumvalue[ m ] [ t ]=sumvalue[ m-1 ]  [ t ]  即第m种药不采的话，所得价值应该和前面采了前面m-1种药且剩余时间为t的价值相等； 这两种情况取最大值就是最优解；

sumvalue[ m ] [ t ]=max {  sumvalue[ m-1 ]  [ t-time[m] ]  +  value[ m ]   ，sumvalue[ m-1 ]  [ t ]  }  ；

实现过程：

void kaicai(int *value,int *time,int M,int T)
{
   int m,t;
   for(m=1;m<=M;m++)
   {
     for(t=1;t<=T;t++)
      {
       if(time[m]<=t)
       sumvalue[m][t]=max(sumvalue[m-1][t-time[m]]+value[m],sumvalue[m-1][t]);
       else
       sumvalue[m][t]=sumvalue[m-1][t];
      }
   }

把sumvalue[ m ] [ t ]打印出来就是这样；

注意事项:
建议去看看01背包，采药太抽象，总的来说，把那个表填出来，再看看多看看；

这是用一维数组解决的：不解释了，太难，把实现部分背得，以后直接用吧。

void kaicai(int *value,int *time,int M,int T)
{
   int m,t;
   for(m=0;m<M;m++)
   {
     for(t=T;t>=time[m];t--)
      {
       if(sumvalue[t-time[m]]+value[m]>sumvalue[t])
        sumvalue[t]=sumvalue[t-time[m]]+value[m];
      }
   }
  printf("%d\n",sumvalue[T]);
}

#include<stdio.h>
void caiyao();
void kaicai(int *value,int *time,int M,int T);
int sumvalue[1000];
/*--------------------------------------------------------------*/
int main()
{
 caiyao();
 return 0;

}

/*--------------------------------------------------------------*/
void caiyao()
{

int T,M;
int value[100],time[100];

while(scanf("%d%d",&T,&M)!=EOF)
{
  for(int i=0;i<M;i++)
  scanf("%d%d",&time[i],&value[i]);

  kaicai(value,time,M,T);
}
return ;
}

/*--------------------------------------------------------------*/
void kaicai(int *value,int *time,int M,int T)
{
   int m,t;
   for(m=0;m<M;m++)
   {
     for(t=T;t>=time[m];t--)
      {
       if(sumvalue[t-time[m]]+value[m]>sumvalue[t])
        sumvalue[t]=sumvalue[t-time[m]]+value[m];
      }
   }
  printf("%d\n",sumvalue[T]);
}

参考代码:

#include<stdio.h>
void caiyao();
void kaicai(int *value,int *time,int M,int T);
int sumvalue[102][1001];
#define  max(x,y) (x)>(y)?(x):(y)

/*--------------------------------------------------------------*/
int main()
{
 caiyao();
 return 0;

}
/*--------------------------------------------------------------*/


void caiyao()
{

int T,M;
int value[100],time[100];

while(scanf("%d%d",&T,&M)!=EOF)
{
  for(int i=1;i<=M;i++)
  scanf("%d%d",&time[i],&value[i]);

  kaicai(value,time,M,T);
}
return ;
}

/*--------------------------------------------------------------*/
void kaicai(int *value,int *time,int M,int T)
{
   int m,t;
   for(m=1;m<=M;m++)
   {
     for(t=1;t<=T;t++)
      {
       if(time[m]<=t)
       sumvalue[m][t]=max(sumvalue[m-1][t-time[m]]+value[m],sumvalue[m-1][t]);
       else
       sumvalue[m][t]=sumvalue[m-1][t];
      }
   }

    /*for(int i=1;i<=M;i++)
    for(int j=1;j<=T;j++)
    {
     printf("%d ",sumvalue[i][j]);
     if(j%T==0)
     printf("\n");
    }*/


    printf("%d\n",sumvalue[M][T]);
}