01背包问题（动态规划）

    动态规划方法通常用来求解最优化问题，这类问题可以有很多可行的解，利用动态规划可以求出其中的一个最优解。可以按照下面的步骤来设计一个动态规划的算法（1）刻画最优解的结构特征（2）递归地定义最优解的值（3）计算最优解的值，可以采用自底向上的方法（4）构造出一个最优解。0-1背包问题是动态规划的常见例子，它的问题描述如下：

   有背包容量为V，有n件物品，他们的体积和价值分别存放在数组v[i]和w[i]中，现欲将物品装入包中，物品的体积之和不得超过包的容量，要使得包中物品的价值量最大，问如何装包。

    假设放入i件物品，第i件物品可以选择放或者不放，如果放入第i件物品可以获得问题的最优解，那么放入前i-1件物品获得问题解是子问题的最优解。建立一个二维数组，f[i][j]，i代表放入物品的数量，j代表背包的容量。将前i件物品放入背包中，如果不放第i件物品，那么问题就转化为前i-1件物品放入剩下容量为j-w[i]的空间内，此时获得的价值是前i-1件物品的价值加上w[i].如果第i件物品选择不放入，那么问题就转换为前i-1件物品放入容量为j的背包中，价值为f[i-1][j].归结起来，是：

可以自底向上地得出在前i件物品中取出若干件物品放入背包所获得的最大价值，算法的程序如下：

# include <iostream>
# include <stdlib.h>
using namespace std;
int V;  //V是背包容量
int I;  //I是物品的数量
int main()
{
int i;
cout<<"input num and cap"<<endl;
cin>>I>>V;
int f(int v[],int w[]);
int v[11];
int w[101];
for (i=1;i<=I;i++)
{
cin>>v[i]>>w[i];
}
cout<<f(v,w)<<endl;
system("pause");
return 0;
}
int max(int x,int y)
{
return x>y?x:y;
}
int f(int v[],int w[])
{
int i,j;
int a[4][11];
for(i=0;i<=3;i++)       //初始化
	for(j=0;j<V;j++)
		a[i][j]=0;
for (i=1;i<=I;i++)     //自底向上地求解最优解
	for(j=0;j<=V;j++)
	{
		if(w[i]<=j)
          a[i][j]=max(a[i-1][j],a[i-1][j-w[i]]+w[i]);
		else
		  a[i][j]=a[i-1][j];
	}
return a[I][V];
}

01背包问题（动态规划）,布布扣,bubuko.com

01背包问题（动态规划）

原文：http://blog.csdn.net/u011608357/article/details/20832153