#include "stdafx.h"
#define N 10
#define W 3
int mv[N][W];
int pack( int (&w)[N],int (&v)[N])
{

    for(int i=0;i<W;++i)  mv[0][i]=0;
    for(int i=0;i&lt;N;++i)  mv[i][0]=0;
    int j,i;
  // DP求解
    for(i=1;i&lt;N;++i)
    {
       for(j=1;j&lt;W;++j)
          if( j >= w[i] )
          {
           if( mv[i-1][j]< mv[i-1][j-w[i]]+v[i])
                mv[i][j] = mv[i-1][j-w[i]]+v[i];
            else
                mv[i][j] = mv[i-1][j];
           }
           else mv[i][j] = mv[i-1][j];
    }
    return  mv[N-1][W-1];
}


int main()
{   
    int w[N]={0,2,3,4,5,6,7,8,9,10},v[N]={0,9,2,3,4,5,2,4,5,3};
    printf("%d",pack(w,v));
    return 0;
}

 

 动态规划中的主要概念，名词术语

    1阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。

    2 状态：某一阶段的出发位置称为状态。通常一个阶段包含若干状态。如图1中，阶段3就有三个状态结点4、5、6。

    3 决策：从某阶段的一个状态演变到下一个阶段某状态的选择。

4策略：由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。

    5 状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。

    6 目标函数与最优化概念：目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。

分析：
    逐步增加包的重量看把当前的包放进去，看能不能得到最优解，选择的测试数据
     int w[N]={0,2,3,4,5,6,7,8,9,10},v[N]={0,9,2,3,4,5,2,4,5,3};
   第0个物品和包的重量为0获得的效益都是0，而且这个解相对于后来也是最优的。。。
   当放入第一个物品的时候，包的重量逐步增加，当包为1时因为物品重为2显然放不下。。所以效益是 mv[i][j] = mv[i-1][j]==0;当包的重量为2时显然可以放下，即j >= w[i]，同时判断效益值，mv[i-1][j]&lt; mv[i-1][j-w[i]]+v[i]
因为子解是最优的，所以只要判断当前是否最优，就可以得到，物品从〇到i，包重量为j时的最优效益。。。下面也是相同分析，我尝试把上面过程安概念分解，大家可以按照概念分下，这是个很经典的题目，很有意思