i3geek.com
闫庚哲的个人博客

dp 背包问题 学习笔记

动态规划的基本思想

将一个问题分解为子问题递归求解,且将中间结果保存以避免重复计算。通常用来求最优解,且最优解的局部也是最优的。求解过程产生多个决策序列,下一步总是依赖上一步的结果,自底向上的求解。

动态规划算法可分解成从先到后的4个步骤:

1. 描述一个最优解的结构,寻找子问题,对问题进行划分。

2. 定义状态。往往将和子问题相关的各个变量的一组取值定义为一个状态。某个状态的值就是这个子问题的解(若有k个变量,一般用K维的数组存储各个状态下的解,并可根    据这个数组记录打印求解过程。)。

3. 找出状态转移方程。一般是从一个状态到另一个状态时变量值改变。

4.以“自底向上”的方式计算最优解的值。

5. 从已计算的信息中构建出最优解的路径。(最优解是问题达到最优值的一组解)

其中步骤1~4是动态规划求解问题的基础,如果题目只要求最优解的值,则步骤5可以省略。

01背包

有N件物品和一个重量为M的背包。(每种物品均只有一件)第i件物品的重量是w[i],价值是p[i]。求解将哪些物品装入背包可使价值总和最大。

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

用子问题定义状态:即c[i][v]表示前i件物品恰放入一个重量为m的背包可以获得的最大价值。则其状态转移方程便是:

c[i][m]=max{c[i-1][m],c[i-1][m-w[i]]+p[i]}

for i=[weight[0],total]
    tab[n-1][i] = weight[0];    //    n为物品数量
for i=[1,n)
    for j=[weight[i],total]
        tab[n-i-1][j] = max(tab[n-i][j-weight[i]]+value[i],tab[n-i][j])
    /*    print tab[0][total]    */

这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入重量为m的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为c[i-1][m];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的重量为m-w[i]的背包中”,此时能获得的最大价值就是c[i-1][m-w[i]]再加上通过放入第i件物品获得的价值p[i]。

测试数据:
10,3
3,4
4,5
5,6

c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.

这个最大价值是怎么得来的呢?从背包重量为0开始,1号物品先试,0,1,2,的重量都不能放.所以置0,背包重量为3则里面放4.这样,这一排背包重量为4,5,6,….10的时候,最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包重量为3的时候,最佳方案还是上一排的最价方案c为4.而背包重量为5的时候,则最佳方案为自己的重量5.背包重量为7的时候,很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包重量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)

public class Pack01 {

	public int [][] pack(int m,int n,int w[],int p[]){
		//c[i][v]表示前i件物品恰放入一个重量为m的背包可以获得的最大价值
		int c[][]= new int[n+1][m+1];
		for(int i = 0;i<n+1;i++)
			c[i][0]=0;
		for(int j = 0;j<m+1;j++)
			c[0][j]=0;
		//
		for(int i = 1;i<n+1;i++){
			for(int j = 1;j<m+1;j++){
				//当物品为i件重量为j时,如果第i件的重量(w[i-1])小于重量j时,c[i][j]为下列两种情况之一:
				//(1)物品i不放入背包中,所以c[i][j]为c[i-1][j]的值
				//(2)物品i放入背包中,则背包剩余重量为j-w[i-1],所以c[i][j]为c[i-1][j-w[i-1]]的值加上当前物品i的价值
				if(w[i-1]<=j){
					if(c[i-1][j]<(c[i-1][j-w[i-1]]+p[i-1]))
						c[i][j] = c[i-1][j-w[i-1]]+p[i-1];
					else
						c[i][j] = c[i-1][j];
				}else
					c[i][j] = c[i-1][j];
			}
		}
		return c;
	}
    /**
     * 逆推法求出最优解
     * @param c
     * @param w
     * @param m
     * @param n
     * @return
     */
    public int[] printPack(int c[][],int w[],int m,int n){
        
        int x[] = new int[n];
        //从最后一个状态记录c[n][m]开始逆推
        for(int i = n;i>0;i--){
            //如果c[i][m]大于c[i-1][m],说明c[i][m]这个最优值中包含了w[i-1](注意这里是i-1,因为c数组长度是n+1)
            if(c[i][m]>c[i-1][m]){
                x[i-1] = 1;
                m-=w[i-1];
            }
        }
        for(int j = 0;j<n;j++)
            System.out.println(x[j]);
        return x;
    }
	public static void main(String args[]){
		int m = 10;
		int n = 3;
		int w[]={3,4,5};
		int p[]={4,5,6};
		Pack01 pack = new Pack01();
		int c[][] = pack.pack(m, n, w, p);
		pack.printPack(c, w, m,n);
	}
}

实际应用

for(i=1;i<=N;i++)
    for(l=V;l>=E[i].v;l--)
        dp[l]=max(dp[l],dp[l-E[i].v]+E[i].val);

 

  完全背包

有N种物品和一个重量为M的背包,每种物品都有无限件可用。第i种物品的重量是w[i],价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包重量,且价值总和最大。

有n种物品,每种物品有无限个,每个物品的重量为weight[i],每个物品的价值为value[i]。现在有一个背包,它所能容纳的重量为total,问:当你面对这么多有价值的物品时,你的背包所能带走的最大价值是多少?

有了上面01背包的式子,这题会变的容易理解很多,只是这个式子要有小小的改动。01背包在二维数组上操作,就是为了防止一个物品被放入多次的情况。因此一维数组可以满足完全背包的问题。如下:

tab[j] = max(tab[j-weight[i]]+value[i],tab[j]);({i,j|0<i<=n,0<=j<=total})

for i=[0,n)
    for(j=weight[i]; j<=total; j++)
        tab[j] = max(tab[j-weight[i]]+value[i],tab[j])
/*    print tab[0][total]    */

实际应用

for(i=0;i<m;i++)
    for(j=b[i];j<=v;j++)
        f[j]=max(f[j],f[j-b[i]]+a[i]);

  多重背包

有N种物品和一个重量为M的背包。第i种物品最多有n[i]件可用,每件重量是w[i],价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包重量,且价值总和最大。

有n种物品,每种物品有amount[i]个,每个物品的重量为weight[i],每个物品的价值为value[i]。现在有一个背包,它所能容纳的重量为total,问:当你面对这么多有价值的物品时,你的背包所能带走的最大价值是多少?

多重和完全更接近,多了数量的限制,用一个count[n]计数数组来限制物品i的数量。当放入第i个物品是较优值的时候,count[i]=count[i-weight[i]]+1;这样做是因为,放入第i个物品的操作是基于count[i-weight[i]]放入的,所以当count[i-weight[i]]>=amount[i]时,就要阻止放入即便放入第i个物品是较优值。

for i=[0,n)
    /*    将count数组清零        */
    for(j=weight[i]; j<=total; j++)
        if    count[i-weight[i]]<amout[i]
            tab[j] = max(tab[j-weight[i]]+value[i],tab[j]);
            if    tab[j]=tab[j-weight[i]]+value[i]    //    决定放入i是较优解
                count[i] = count[i-weight[i]] + 1
        else    if    tab[j]=0        //    防止装第1个物品和装其他物品的情况
            tab[j] = tab[j-1],count[j] = count[j-1]
        else    count[j] = count[j-1]
/*    print tab[0][total]    */

 

 

赞(0)
未经允许不得转载:爱上极客 » dp 背包问题 学习笔记
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址