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