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 
  
   
# include 
   
     using namespace std; int V; //V是背包容量 int I; //I是物品的数量 int main() { int i; cout<<"input num and cap"<
    
     >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<
     
      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