0-1背包问题：下面的递推关于i的循环是逆向进行的。反之，如果将d[i+1][j]定义成从0到i这i+1个物品中选出总重量不超过j的物品时总价值的最大值的话，关于i的循环就能正向进行。
普通搜索：
#include<iostream>
#include<cmath>
using namespace std;
int n,w;
int w1[110],v[110];int rec(int i,int j){ //从第i个物品开始挑选总重不超过j的部分int res;if(i==n) res=0; //已经没有剩余物品了else if(j<w1[i])res=rec(i+1,j); //无法挑选这个物品else{res=max(rec(i+1,j),rec(i+1,j-w1[i])+v[i]); }return res;
}int main()
{cin>>n>>w;for(int i=0;i<n;i++)cin>>w1[i]>>v[i];int res=rec(0,w);cout<<res<<endl;return 0;
}/*
4 5
2 3
1 2
3 4
2 2
*/记忆化搜索：
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=110;
const int maxw=10010;
int n,w,dp[maxn][maxw];
int w1[110],v[110];int rec(int i,int j){ //从第i个物品开始挑选总重不超过j的部分int res;if(dp[i][j]>=0) return dp[i][j];if(i==n) res=0; //已经没有剩余物品了else if(j<w1[i])res=rec(i+1,j); //无法挑选这个物品else{res=max(rec(i+1,j),rec(i+1,j-w1[i])+v[i]);}return dp[i][j]=res;
}int main()
{cin>>n>>w;for(int i=0;i<n;i++)cin>>w1[i]>>v[i];memset(dp,-1,sizeof(dp));int res=rec(0,w);cout<<res<<endl;return 0;
}/*
4 5
2 3
1 2
3 4
2 2
*/记忆化递归转成递推（动规）：
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=110;
const int maxw=10010;
int n,w,dp[maxn][maxw]; //由前面的记忆化递归可知，dp[i][j]从第i个物品开始挑选总重不超过j时，总价值的最大值
int w1[110],v[110];int main()
{cin>>n>>w;for(int i=0;i<n;i++)cin>>w1[i]>>v[i];for(int i=0;i<=w;i++)dp[n][0]=0;for(int i=n-1;i>=0;i--){for(int j=0;j<=w;j++){if(j<w1[i]) dp[i][j]=dp[i+1][j];else dp[i][j]=max(dp[i+1][j],dp[i+1][j-w1[i]]+v[i]);}}cout<<dp[0][w]<<endl;return 0;
}/*
4 5
2 3
1 2
3 4
2 2
*/