题目大意：有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 ;
}