八戒找宝藏(动态规划求解0/1背包问题)

有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值的宝石总和？

假设有4个物品，他们的体积，价值分别为w,c.

根据动态规划解题步骤找出0/1背包问题的最优解以及解组成，然后编写代码实现。动态规划是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接从表格中提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

       首先需要定义一些变量：m表示背包总重量，n表示宝石总数，w[i]表示第i个宝石的重量，c[i]表示第i个宝石的价值，f数组存储对应的总价值。

1、循环输入宝石重量与对应价值;

2、动态求解每一个小问题:宝石个数为i，背包大小为j;

3、设f[i,j]表示前i块宝石，背包容量为j时的最优价值;

        包的容量比该宝石体积小，装不下，此时的价值与前i-1个的价值是一样的，即f[i][j] = f[i - 1][j];
还有足够的容量可以装该宝石，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即f[i][j] = max(f[i - 1][j - w[i]] + c[i],f[i - 1][j]).

关系式：

1.     j < w[i]:        f[i - 1][j];
2.     j >= w[i]:      max(f[i - 1][j - w[i]] + c[i],f[i - 1][j]);

       第一种是第i件宝石没有装进去，第二种是第i件宝石装进去了。如果没有装进去就是f[i - 1][j];，如果装进去了，那么装入之前是f[i - 1][j]，装入之后是max(f[i - 1][j - w[i]] + c[i],f[i - 1][j])，两种情况进行比较，得出最优。

4、使用for循环填表;

5、表格填完，最优解即是f(4,8)=10。

#include
using namespace std;
//w,c数组分别存储重量与价值
//f数组存储对应的总价值 
int w[200],c[200],f[200][200];
int main(){
	//1 m表示背包总重量，n表示宝石总数 
	int m,n;
	cin >> m >> n;
	//2 循环输入宝石重量与对应价值 
	for(int i = 1;i <= n;i++){
		cin >> w[i] >> c[i];
	}
	//3 动态求解每一个小问题:宝石个数为i，背包大小为j
	//设f(i,j)表示前i块宝石，背包容量为j时的最优价值 
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			//若当前背包容量能装得下当前宝石 
			if(j >= w[i]){
				f[i][j] = max(f[i - 1][j - w[i]] + c[i],f[i - 1][j]);
			} else {
				//当前最优解 
				f[i][j] = f[i - 1][j];
			}
		}
	}
	//输出最终优解 
	cout << f[n][m] << endl;
return 0;
}

通过上面的代码可以求出背包问题的最优解.