HDU 2602 Bone Collector - from lanshui_Yang

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

上一篇:angularjs揭秘


下一篇:Python使用Socket写一个简单聊天程序