逆推求解c++

解题思路:经典的01背包问题，本题只需要最后结果，在优化算法中用一维数组去求解，因为每轮中只需要第i-1阶段的结果去更新第i阶段。

注意事项:背包容量的一维数组是需要从0-m；所以定义数组的时候需要m+1.

参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

int main(){

int n=0,m=0;

cin>>n>>m;//n个物品，m容量

int w[n];//物品重量 

int v[n];//物品价值 

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

cin>>w[i]>>v[i];

}

//这部分我在初始化放入零

int maxv[m+1];

for(int i=0;i<=m;i++)

{

maxv[i]=0;

}

for(int i=0;i<n;i++)

{

for(int j=m;j>=w[i];j--)

{

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

}

}

cout<<maxv[m]<<endl;

return 0;

}