从背包问题优化详解动态规划思想_动态规划编写背包程序基本思想

动态规划：

一、基本概念：任何数学递推公式都可以直接转换成递归算法，但是基本现实是编译器常常不能正确对待递归算法，结果导致低效的程序。当怀疑很可能是这种情况是，我们必须给编译器提供一些帮助，将递归算法重新写成非递归算法让后者把这些子问题的答案系统地记录在一个表内。利用这种方法的一种技巧叫做动态规划。根据《数据结构与算法分析--Java语言描述》原书第三版 中给动态规划（DP）的定义（出自《数据结构与算法分析--Java语言描述》原书第三版 ）

二、主要分类：动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
举例：
线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
背包动规：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶等；
除此之外还有许多变形的动态规划问题，再次不一一列举。

三、动态规划问题中的术语（这一部分看不懂没关系，用处不大）

阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同。描述阶段的变量称为阶段变量。
状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在具体题目中，状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。
无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展。
决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。
策略：由每个阶段的决策组成的序列称为策略。集合中达到最优效果的策略称为最优策略。

最优化原理:作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。一个问题满足最优化原理也称其拥有最优子结构性质。最优性原理实际上是要求问题的最优策略的子策略也是最优。

四、基本思想：动态规划思想通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但是适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

五、解题思路：

1.找出最优解的性质，刻画其结构特征和最优子结构特征；
2.递归地定义最优值，刻画原问题解与子问题解间的关系，找到状态方程；
3.以自底向上的方式计算出各个子问题最优解，并避免子问题的重复计算；
4.根据计算最优值时得到的信息，构造最优解。

01背包

有N件物品和一个容量为C的背包。第i件物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

 从这个题目中可以看出，01背包的特点就是：每种物品仅有一件，可以选择放或不放。

输入：第一行两个数据，物品件数N，背包容量C

接下来N行，每行对应第i件物品的体积v[i]和价值w[i]

Input：

3 9

1 2

2 3

3 1

Output：

6

思路一：逆向规划

我们假定当前阶段的状态d(i, j)表示当前第i层，将从第i个到第n个物品装入容量为j的背包所能达到的最大重量

由此，规划的终点就是d(1, c)[即代表将第1，2,3，...，n个物品装入容量为G的背包中所能达到的最大重量]

规划的起点就是d(n, 0) 或 d(n, c)

如果我们不放物品i，状态转移为d(i+1, j)，即将物品i+1放入剩余容量仍为j的背包中的价值

如果我们放入物品i，状态转移为d(i+1, j-v[i])+w[i], 即将物品i+1放入剩余容量为j-v[i]的背包中的价值

状态转移方程：d(i, j) = max{d(i+1, j), d(i+1, j-v[i]) + w[i]}

import java.util.Scanner;
 
 
public class Main {
    static Scanner in = new Scanner(System.in);
    static int[] v,w;
    static int[][] d;
    static int n, c;
    public static void main(String[] args) {
        n = in.nextInt();
        c = in.nextInt();
        v = new int[n+1];
        w = new int[n+1];
        d = new int[n+2][c+1];
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        for(int i = n; i >= 1; i--) {
            for(int j = 0; j <= c; j++) {
                d[i][j] = (i==n ? 0 : d[i+1][j]);
                if(j >= v[i]) {
                    d[i][j] = Math.max(d[i][j],d[i+1][j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(d[1][c]);
    }
}

思路二：正向规划

 
import java.util.Scanner;
 
 
public class Main {
    static Scanner in = new Scanner(System.in);
    static int[] v,w;
    static int[][] d;
    static int n, c;
    public static void main(String[] args) {
        n = in.nextInt();
        c = in.nextInt();
        v = new int[n+1];
        w = new int[n+1];
        d = new int[n+1][c+1];
        for(int i = 1; i <= n; i++) {
            int v = in.nextInt();
            int w = in.nextInt();
            for(int j = 0; j <= c; j++) {
                d[i][j] = (i==1 ? 0 : d[i-1][j]);
                if(j >= v) {
                    d[i][j] = Math.max(d[i][j],d[i-1][j-v]+w);
                }
            }
        }
        System.out.println(d[n][c]);
    }
}

思路三：用滚动数组实现

我们假定当前阶段的状态d(j)表示将当前物品装入容量为 j 的背包所能达到的最大重量

规划的起点d( 0 )

规划的终点d( c )

状态转移方程：d( j ) = max{d( j ), d( j - v) + w}

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

在这类求最优解的背包问题中，有的题目要求“恰好装满背包”时的最优解，而有的题目则并没有要求必须装满。

区别这两种问法的实现方法是在初始化的时候有所不同。

如果是要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。