01背包问题

题目：有A（2kg，6$）；B（2kg，3$）；C（6kg，5$）；D（5kg，4$）；E（4kg，6$）五种物品各一件，括号内标示该物品的重量和价值，假设你有一个容量为10kg的背包来装上述物品，试求出可以装下的最大价值。

分析：若装了c物品后达到了最大价值

-------------------当前最大价值 =（背包总重量-c物品重量）时的最大价值+c物品的价值----------------

每件物品的考虑方式：

    1st:该物品重量是否大于背包总重量，大于则无法装入背包；

    2nd:若能装入背包：

        v1=当前最大价值 =（背包总重量-该物品重量）时的最大价值+c物品的价值

       v2=不装该物品时背包最大价值

        选v1和v2中较大者。

物品重量数组：w[6]={0,2,2,6,5,4}     //增加数组长度便与代码编写，

物品价值数组：v[6]={0,6,3,5,4,6}    //增加数组长度便与代码编写，

动态规划二维辅助数组：dp[6][11]   //增加数组长度便与代码编写，并将第一行,列初始为0

---------------------dp[i][j]表示在前i个物品中用容量为j的背包可以装入的最大价值-------------------

状态转移方程：

------------------------------------dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}-----------------------------------

核心代码：

for（j=0;j<10;j++)

{ 

    for(i=1;i<5;i++)

    { 

        if(w[i]>j)  dp[i][j]=dp[i-1][j];

            else 

            {

            int v1=dp[i-i][j-w[i]]+v[i];

            int v2=dp[i-1][j];

            if(v1>v2) dp[i][j]=v1;

                else 

                {

                dp[i][j]=v2;

                }

            }

    }

}