动态规划通用题解，学会了就都懂了

解题思路:二维数组填表来实现

注意事项:vtype代表的是价值和体重的类型

如果可以，自己实现一个函数不用max函数是最优解，即可达到动态规划公式

参考代码:

#include <iostream>

using namespace std;

#define maxn 201 //总共多少个物品 

#define maxv  5001 //总共多大容量 

#define inf -1

#define init 0

#define vtype int 

//int otj(int a,int b){

// if()

//}

//物品数   背包最大容量     所有物品的重量   所有物品的价值     dp数组 

void knapsack01(int N,int V,int weight[maxn],vtype value[maxn],vtype dp[maxn][maxv]){

for(int i=1;i<=V;++i){

dp[0][i]=inf;

}

dp[0][0]=init;

for(int i=1;i<=N;++i){

for(int j=0;j<=V;++j){

if(j>=weight[i]){

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 weight[maxn];

vtype value[maxn];

vtype dp[maxn][maxv];

int main(){

int V,N;

cin>>N>>V;

for(int i=1;i<=N;++i){

cin>>weight[i]>>value[i];

}

knapsack01(N,V,weight,value,dp);

vtype ret=0;

for(int i=0;i<=V;++i){

ret=max(ret,dp[N][i]);

}

cout<<ret<<endl;

}