01背包，动态规划算法

0-1背包问题：给定n种物品和一个容量为c的背包，物品i的重量是wi,其价值是vi

问：应该怎样选择装入背包的物品，使得装入背包的物品的总价值最大？

解：声明一个大小为m[n][c]的二维数组，m[i][j]表示在面对第i间物品，且背包容量为j时所能获得的最大价值，我们就可以分析出m[i][j]的计算方法

（1）.j<w[i]的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿

m[i][j]=m[i-1][j]

(2).j>=w[i]的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。如果拿取，m[i][j]=m[i-1][j-w[i]]+v[i]。这里的m[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品，背包容量为j-w[i]时的最大价值，也是相当于为第i件物品腾出了w[i]的空间。

如果不拿，m[i][j]=m[i-1][j]

由此可以得到状态转移方程：

if(j>=w[i])
    m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
else
    m[i][j]=m[i-1][j];

本题代码：

#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];

      }

   }

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

}