动态规划解决0-1背包问题_采用动态规划法求解 0-1 背包问题。问题描述:有 n 个物品,它们有各自的重量 和价

0-1背包问题：给定n种物品和一背包。物品 i 的重量似乎 wi，其价值为 vi，背包的容量为 c。问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

例子：

（ 1）问题描述
给定几组数据，利用动态规划算法的思想，把 0-1 背包装满并使得其价值最大。
（ 2）实验步骤
① 把问题分解成若干个子问题，如背包仅可以容纳 1 个物品且可以容纳 的质量为一等。
② 依次求出各个子问题的最优解。
③ 每个子问题的最优解又可以从它的子问题的最优解中得到。
④ 通过各个子问题的最优解得到原问题的最优解。
c++代码实现代码如下：

#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
struct Thing{
	int weight;
	int value;
};
int main(int argc, char** argv) {
	int n;
	cout<<"input the number of things:"<<endl;
	cin>>n;
	int c;
	cout<<"input the capacity of the bag:"<<endl;
	cin>>c;
	Thing things[n];
	for(int i=0;i<n;i++){
		cin>>things[i].weight;
		cin>>things[i].value;
	}
	
	// 构造最优解的网格:n行c列
    int maxValue[n][c];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < c; j++) {
            maxValue[i][j] = 0;
        }
    } 
	for(int i=0;i<n;i++){
		for(int j=1;j<=c;j++){
			if(i==0){
				maxValue[i][j-1] = (j>=things[i].weight ? things[i].value : 0);
			}else{
				int topValue=maxValue[i-1][j-1];
				int curValue=(things[i].weight<=j ? 
				    (j-things[i].weight>0 ? maxValue[i-1][j-things[i].weight]+things[i].value : things[i].value):topValue);
				maxValue[i][j-1]=(curValue > topValue ? curValue:topValue);
			}
		}
	}
	for (int i = 0; i < n; i++) {
        for (int j = 0; j < c; j++) {
            cout<<maxValue[i][j];
            cout<<" ";
        }
        cout<<endl;
    } 
	system("pause");
	return 0;
}

参考：https://www.jianshu.com/p/a66d5ce49df5