最基础的背包问题：每种物品仅有一件，可以选择放或者不放！

    动态转移方程：f[i, v] = max {  f [i-1][v] ,    f [i-1] [j - c[i] ]+w[i]  } ;

                                          // 不放第 i 件     // 如果放进去（但是要保证放进去前，剩余空间够大 ）

                                          比较这两项的价值，我们会选择最大的 放进背包里！

   0-1背包：两种方式！

   （1）建立二维数组 f [N][N];

         伪代码： for( i=1 ->  n )

                          {

                             for( j=1 ->  v  )

                                {

                                     dp[i][j] = dp[i-1][j];
                                      if(j>=p[i])
                                             f [i][j] = max( f [i-1][j],   f [i-1][ j-c [i] ]+w[i]  ) ;

                                 }

                           }

 *******************************

#include <stdio.h>#define N 1006int dp[N][N], w[N], p[N];int max(int a, int b){	return a > b ? a : b;}void main(){	int t, n, v,i, j;	scanf("%d", &t);	while(t--)	{		scanf("%d %d", &n, &v);		for(i=1; i<=n; i++)		{			scanf("%d", &w[i]);		}		for(i=1; i<=n; i++)		{			scanf("%d", &p[i]);		}		for(i=0; i<=n; i++)		{			dp[i][0] = 0;		}		for(i=0; i<=v; i++)		{			dp[0][i] = 0;		}		for(i=1; i<=n; i++)		{			for(j=0; j<=v; j++)			{				dp[i][j] = dp[i-1][j];				if(j>=p[i]) //前提是背包放得下，j代表背包体积， p[i]代表花费					dp[i][j] = max(dp[i-1][j-p[i]]+w[i], dp[i-1][j]);			}		}		printf("%d\n", dp[n][v]);	}}

   (2) 建立一维数组 f [N]

        伪代码：

        memset( f, 0, sizeof( f ) );

        for(i=1; i<=n; i++)
        {
            for(j=v; j>=c[i]; j-- )
            {
                f [j] = max (  f [j],  f[ j- c[i] ] + w[i] );

            }
        }