动态规划——01背包

转 https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html

问题描述：有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

三、动态规划的原理及过程：

　　eg：number＝4，capacity＝8

i

1

2

3

4

w(体积)

2

3

4

5

v(价值)

3

4

5

6

      定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值；

　  寻找递推关系式，面对当前商品有两种可能性：

　　　　第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；

　　　　第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝

　　　　　　　其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；

　　　　由此可以得出递推关系式：

　　　　1) j<w(i)      V(i,j)=V(i-1,j)

　　　　2) j>=w(i)     V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝

　 填表，首先初始化边界条件，V(0,j)=V(i,0)=0；

 

　　h) 然后一行一行的填表，

　　　　1) 如，i=1，j=1，w(1)=2，v(1)=3，有j<w(1)，故V(1,1)=V(1-1,1)=0；

　　　　2) 又如i=1，j=2，w(1)=2，v(1)=3，有j=w(1),故V(1,2)=max｛ V(1-1,2)，V(1-1,2-w(1))+v(1) ｝=max｛0，0+3｝=3；

　　　　3) 如此下去，填到最后一个，i=4，j=8，w(4)=5，v(4)=6，有j>w(4)，故V(4,8)=max｛ V(4-1,8)，V(4-1,8-w(4))+v(4) ｝=max｛9，4+6｝=10；所以填完表如下图：

 

void FindMax()//动态规划
{
    int i,j;
    //填表
    for(i=1;i<=number;i++)
    {
        for(j=1;j<=capacity;j++)
        {
            if(j<w[i])//包装不进
            {
                V[i][j]=V[i-1][j];
            }
            else//能装
            {
                if(V[i-1][j]>V[i-1][j-w[i]]+v[i])//不装价值大
                {
                    V[i][j]=V[i-1][j];
                }
                else//前i-1个物品的最优解与第i个物品的价值之和更大
                {
                    V[i][j]=V[i-1][j-w[i]]+v[i];
                }
            }
        }
    }
}

View Code

 

　　i) 表格填完，最优解即是V(number,capacity)=V(4,8)=10，但还不知道解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表的原理可以有如下的寻解方式：

　　　　1) V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)；

　　　　2) V(i,j)=V(i-1,j-w(i))+v(i)实时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；

　　　　3) 一直遍历到i＝0结束为止，所有解的组成都会找到。

　　j) 如上例子，

　　　　1) 最优解为V(4,8)=10，而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10，所以第4件商品被选中，并且回到V(3,8-w(4))=V(3,3)；

　　　　2) 有V(3,3)=V(2,3)=4，所以第3件商品没被选择，回到V(2,3)；

　　　　3) 而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4，所以第2件商品被选中，并且回到V(1,3-w(2))=V(1,0)；

　　　　4) 有V(1,0)=V(0,0)=0，所以第1件商品没被选择；

 

　　k) 到此，01背包问题已经解决，利用动态规划解决此问题的效率即是填写此张表的效率，所以动态规划的时间效率为O(number*capacity)=O(n*c)，由于用到二维数组存储子问题的解，所以动态规划的空间效率为O(n*c)；

void FindWhat(int i,int j)//寻找解的组成方式
{
    if(i>=0)
    {
        if(V[i][j]==V[i-1][j])//相等说明没装
        {
            item[i]=0;//全局变量，标记未被选中
            FindWhat(i-1,j);
        }
        else if( j-w[i]>=0 && V[i][j]==V[i-1][j-w[i]]+v[i] )
        {
            item[i]=1;//标记已被选中
            FindWhat(i-1,j-w[i]);//回到装包之前的位置
        }
    }
}

View Code

 

3、空间优化

　　l) 空间优化，每一次V(i)(j)改变的值只与V(i-1)(x) {x:1...j}有关，V(i-1)(x)是前一次i循环保存下来的值；

　　因此，可以将V缩减成一维数组，从而达到优化空间的目的，状态转移方程转换为 B(j)= max{B(j), B(j-w(i))+v(i)}；

　　并且，状态转移方程，每一次推导V(i)(j)是通过V(i-1)(j-w(i))来推导的，所以一维数组中j的扫描顺序应该从大到小(capacity到0)，否者前一次循环保存下来的值将会被修改，从而造成错误。

 

　

void FindMaxBetter()//优化空间后的动态规划
{
    int i,j;
    for(i=1;i<=number;i++)
    {
        for(j=capacity;j>=0;j--)
        {
            if(B[j]<=B[j-w[i]]+v[i] && j-w[i]>=0 )//二维变一维
            {
                B[j]=B[j-w[i]]+v[i];
            }
        }
    }
}

View Code

 

　然而不足的是，虽然优化了动态规划的空间，但是该方法不能找到最优解的解组成，因为动态规划寻找解组成一定得在确定了最优解的前提下再往回找解的构成，而优化后的动态规划只用了一维数组，之前的数据已经被覆盖掉，所以没办法寻找，所以两种方法各有其优点。

完整代码：

import java.util.*;

public class backpack01 {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int[] w = new int[1005];
        int[] v = new int[1005];
        int[] dp = new int[1005]; dp[0]=0;
        
        int n = scanner.nextInt();
        int c = scanner.nextInt();
        for(int i=1;i<=n;i++) {
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }
        
        for(int i=1;i<=n;i++)
            for(int j=c;j>=w[i];j--) {
                dp[j] = Math.max(dp[j], dp[j-w[i]]+v[i]); 
            }
        System.out.println(dp[c]);
    }
}

View Code