0-1背包问题

题目

一个背包总容量为V，现在有N个物品，第i个物品体积为weight[i]，价值为value[i]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？
(0-1背包问题指的是每个物品只能使用一次)

思路

定义一个二维数组dp[][]，大小为N×V
dp[i][j]：把前i个物品（从第1个到第j个）装入容量为j的背包中获得的最大价值
从dp[0][0]递推到dp[N][V]

现在递推dp[i][j]，分两种情况
1、第i个物品的体积比容量j大，装不进去 dp[i][]=dp[i-1][j]

2、第i个物品的体积比容量j小，能装进去(这时候再分两种情况：装或不装第i个物品)
不装第i个: dp[i][j]=dp[i-1][j]
装第i个: dp[i][j]=dp[i-1][j-weight[i]]+value[i]

代码

#includeusing namespace std;const int N=10000;int weight[N];int value[N]; int dp[N][N];int solve(int i,int j){if(dp[i][j]!=0){    //记忆化 return dp[i][j];}if(weight[i]>j){dp[i][j]=solve(i-1,j);}else{dp[i][j]=max(solve(i-1,j),solve(i-1,j-weight[i])+value[i]);}return dp[i][j];}int main(){int N,V;cin>>N>>V;for(int i=0;i<N;i++){cin>>weight[i]>>value[i];}memset(dp,0,sizeof(dp));cout<<solve(N,V)<<endl; return 0;}