0-1背包(DP经典问题)

有n个重量和价值分别为wi,vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。

方案一：dp[i][j]表示1~i号物品放到体积为j的背包中的最大值

状态转移方程为：

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

实现：可自底向上和自顶向下

自底向上：

dp[N+1][V+1]; memset(dp,0,sizeof(dp)); for(int i=1;i<=N;i++){//物品 for(int j=0;j<=V;j++){//体积 if(j-weight[i]>=0){ dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]); } else{ dp[i][j]=dp[i-1][j]; } } } 自顶向下：

int dp[N+1][V+1]; int DP(int n,int v){ if(n<=0||v<=0){ return 0; } if(dp[n][v]>=0){ return dp[n][v]; } if(v-weight[n]>=0){ return dp[n][v]=max(DP(n-1,v),DP(n-1,v-weight[n])+value[n]); } else{ return dp[n][v]=DP(n-1,v); } } int main(){ memset(dp,-1,sizeof(dp)); cout<<DP(N,V)<<endl; return 0; }方案二：

dp[i][j]表示从第i个物品开始挑选物品使总重小于j的情况的最大值

状态转移方程：

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

实现：自顶向下和自底向上

自顶向下：

int dp[N+1][V+1]; int DP(int n,int v){ if(n>N||v<=0){ return 0; } if(dp[n][v]>=0){ return dp[n][v]; } if(v-weight[n]>=0){ return dp[n][v]=max(DP(n+1,v),DP(n+1,v-weight[n])+value[n]); } else{ return dp[n][v]=DP(n+1,v); } } int main(){ memset(dp,-1,sizeof(dp)); cout<<DP(1,V)<<endl; return 0; }自底向上：

int dp[N+2][V+1]; memset(dp,0,sizeof(dp));//为了使dp[N+1][j]为0 for(int i=N;i>=1;i--){ for(int j=0;j<=V;j++){ if(j-weight[i]>=0){ dp[i][j]=max(dp[i+1][j],dp[i+1][j-weight[i]]+value[i]); } else{ dp[i][j]=dp[i+1][j]; } } } cout<<dp[1][V]<<endl;//可以看出：

//对于自顶向下实现的DP,要考虑怎么初始化dp数组，从而能判断dp数组为何值代表已经算过了，避免重复计算。同时也要考虑递归出口，即状态转移方程的边界条件。

//对于自底向实现的DP,要考虑怎么初始化dp数组，从而能适用于状态转移方程的边界条件。