题目大意：有n件物品，每件物品均有各自的价值和体积，给你一个容量为 V 的背包，问这个背包最多能装的物品的价值是多少？

       解题思路：这是一道0 - 1 背包的简单模板题，也是基础的DP问题，状态转移方程 

                     f[i][j] = max{ f[ i - 1 ][j] , f[ i - 1 ][ j - v[i] ] + w[i]  }

        边界条件：f[0][0] = f[0][1] = ……  = f[0][ V ] = 0 ;   

这是我的第一道DP，为了纪念一下，我练习了三种解法，如有错误，敬请读者指出。

#include <iostream>

#include<cstring>

#include<algorithm>

#include<string>

#include<cmath>

#include<cstdio>

using namespace std;

const int MAXN = 1111 ;

int n , V ;

int w[MAXN] ;  // 物品的价值

int v[MAXN] ;  // 物品自身的体积

int f[MAXN][MAXN] ;

bool vis[MAXN][MAXN] ;

int f2[MAXN] ;

void init()

{

    scanf("%d%d" , &n , &V) ;

    int i ;

    for(i = 1 ; i <= n ; i ++)

    {

        scanf("%d" , &w[i]) ;

    }

    for(i = 1 ; i <= n ; i ++)

    {

        scanf("%d" , &v[i]) ;

    }

}

void solve1() // 普通解法

{

    int i , j ;

    for(j = 0 ; j <= V ; j ++)

    {

        f[0][j] = 0 ;

    }

    for(i = 1 ; i <= n ; i ++)

    {

        for(j = 0 ; j <= V ; j ++)

        {

            f[i][j] = f[i - 1][j] ;

            if(j >= v[i])

            f[i][j] = max(f[i - 1][j] , f[i - 1][j - v[i]] + w[i]) ;

        }

    }

    printf("%d\n" , f[n][V]) ;

}

void solve2()  // 滚动数组解法

{

    memset(f2 , 0 , sizeof(f2)) ;

    int i , j ;

    for(i = 1 ; i <= n ; i ++)

    {

        for(j = V ; j >= 0 ; j --)

        {

            if(j >= v[i])

            f2[j] = max(f2[j] , f2[ j - v[i] ] + w[i]) ;

        }

    }

    printf("%d\n" , f2[V]) ;

}

int dp(int i , int j)

{

    int& ans = f[i][j] ;

    if(vis[i][j])

    return f[i][j] ;

    if(i == 0)

    ans == 0 ;

    else

    {

        ans = dp(i - 1 , j) ;

        if(j >= v[i])

        ans = max(dp(i - 1 , j) , dp(i - 1 , j - v[i]) + w[i] ) ;

    }

    vis[i][j] = true ;

    return ans ;

}

void solve3()  // 用记忆化搜索（memoization）求解，完全按照状态转移方程来写，较易理解。

{

    memset(vis , 0 , sizeof(vis)) ; // 初始化标记数组

    printf("%d\n" , dp(n , V)) ;

}

int main()

{

    int T ;

    scanf("%d" , &T) ;

    while (T --)

    {

        init() ;

        solve1() ;

        solve2() ;

        //solve3() ;

    }

    return 0 ;

}