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

n=4;

(w,v)={(2,3),(1,2),(3,4),(2,2)}

W=5；

 

输出：7    （选0号,1号,3号）

理解：

//n个物品 背包容量W 
//int w[max_n],v[max_n];    weight,value; 



//暴搜  O(2^n)
int rec(int i,int j){ 
	int res;               
	if(i==n){
		res=0;
	}
	else if(j<w[i]){
		res=rec(i+1,j);  //物品重量超重，不选，i++,看下一个 
	}
	else {
		res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
	}                     //不超重情况下，每次选或者不选，全部枚举 
	return res;
}
void sovle(){
	cout<<rec(0,W);
} 



//记忆化搜索 O(nW)
int dp[max_n][max_n];
int rec(int i,int j){
	if(dp[i][j]>=0){
		return dp[i][j];
	}
	int res;
	if(i==n){
		res=0;
	}
	else if(j<w[i]){
		res=rec(i+1,j);
	}
	else{
		res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
	}
	return dp[i][j]=res;
} 



//dp1 O(mn)
//dp[i][j]从0到i,这n+1个物品中选出总重不超过j的物品时货物的最大价值 
dp[0][j]=0;
if(j<w[i])  
dp[i+1][j]=dp[i][j]; //装不下第i个  
else 
dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]) ;//装或不装对于价值增加大的


void sovle(){
	for(int i=0;i<n;i++){
		for(int j=0;j<=W;j++){
			if(j<w[i]){
				dp[i+1][j]=dp[i][j];
			} 
			else {
				dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
			}
		}
	}
	cout<<dp[n][w];
}  


//dp2 
//从dp1的基础上，状态转移变为：
//前i+1个物品中选取总重不超过j和前i+1个物品中选取总重不超过j+w[i];
 
void sovle(){
	for(int i=0;i<n;i++){
		for(int j=0;j<=W;j++){
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
			if(j+w[i]<=W){
			dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]);	
			}
		}
	}
	cout<<dp[n][W];
}


//dp3

int dp[max_n];
void sovle(){
	for(int i=0;i<n;i++){
		for(int j=W;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[W];
}

 

最终代码 ：

#include<bits/stdc++.h> 
using namespace std;
const int MAX_N=10000;
int n,W; 
int w[MAX_N],v[MAX_N];
int dp[MAX_N+1];
void solve(){
	for(int i=0;i<n;i++){
	for(int j=W;j>=w[i];j--){
	   	dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		   }
	   }
	printf("%d\n",dp[W]);
}
int main(){
	scanf("%d %d",&n,&W);
	for(int K=0;K<n;K++)
	{
		scanf("%d %d",&w[K],&v[K]);
	}
	solve();
	return 0;
}