动太规划

动太规划问题有很多，这里只讨论两个问题：

1. 取子数组的最大和
2. 01背包问题

参考：
算法之美：动态规划 - Bourbon - 博客园
动态规划之01背包问题（最易理解的讲解） - CSDN博客

取子数组的最大和

一般实现：两次循环遍历

/**
 * 取子数组的最大和
 */
public class CommonTest {
    public static void main(String[] args) {
        int[] a = {0, -2, 3, 5, -1, 2};
        System.out.println(MaxSubString(a));
    }

    /**
     * 一般解法：两次循环遍历
     *
     * @param a
     * @return
     */
    static int MaxSubString(int[] a) {
        int max = -1000;  //初始值为负无穷大
        int sum;
        for (int i = 0; i < a.length; i++) {
            sum = 0;
            for (int j = i; j < a.length; j++) {
                sum += a[j];
                if (sum > max)
                    max = sum;
            }
        }
        return max;
    }
}

动太规划实现：

public class BetterTest {
    public static void main(String[] args) {
        int[] a = {0, -2, 3, 5, -1, 2};
        System.out.println(maxSubStr(a));
    }

    /**
     * 动态规划：取子数组的最大和
     * 动态规划解法：
     * <p>
     * 设sum[i]为以第i个元素结尾且和最大的连续子数组。假设对于元素i，
     * 所有以它前面的元素结尾的子数组的长度都已经求得，那么以第i个元素结尾且和最大的连续子数组实际上，要么是以第i-1个元素结尾且和最大的连续子数组加上这个元素，
     * 要么是只包含第i个元素，即sum[i] = max(sum[i-1] + a[i], a[i])。
     * 可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择，而这实际上等价于判断sum[i-1]是否大于0。
     * 由于每次运算只需要前一次的结果，因此并不需要像普通的动态规划那样保留之前所有的计算结果，只需要保留上一次的即可，
     * 因此算法的时间和空间复杂度都很小。
     * <p>
     * eg:
     * 0, -2, 3, 5, -1, 2
     * sum=3, 5=8
     * result=8
     * sum=3, 5,-1=7
     * result=8
     * sum=3, 5,-1, 2=9
     * result=9
     *
     * @param a
     * @return
     */
    static int maxSubStr(int[] a) {
        int result = Integer.MIN_VALUE;
        int sum = Integer.MIN_VALUE;//临时数据，存储包含“子数组的最大和”的连续字符串
        for (int i = 0; i < a.length; i++) {
            if (sum > 0)
                sum += a[i];
            else
                sum = a[i];
            if (sum > result)
                result = sum;
        }
        return result;
    }
}

01背包问题

代码实现：

public class Pack01 {
    /**
     * f[i][j] 为第i
     * f[i][j] = getMax(f[i - 1][j], f[i - 1][j - c[i]] + v[i]);//转移方程式
     *
     * @param args
     */
    public static void main(String[] args) {
        int c[] = {3, 5, 2, 7, 4};//体积
        int v[] = {2, 4, 1, 6, 5};//价值
        int f[][] = new int[5][11];

   /*  1 2 3 4 5 6 7 8 9 10
   3 2 0 0 2 2 2 2 2 2 2 2
   5 4 0 0 2 2 4 4 4 6 6 6
   2 1 0 1 2 2 4 4 5 6 6 7
   7 6 0 1 2 2 4 4 6 6 7 8
   4 5 0 1 2 5 5 6 7 7 9 9
    */
        for (int i = 0; i < 5; i++) {
            System.out.println();
            System.out.print("『" + i + "』" + c[i] + " " + v[i] + "--->");
            for (int j = 1; j <= 10; j++) {
                if (i == 0) {
                    f[0][j] = j > v[0] ? v[0] : 0;
                    System.out.print(f[i][j] + " ");
                    continue;
                }
                if (c[i] > j)//如果背包的容量，放不下c[i]，则不选c[i]
                    f[i][j] = f[i - 1][j];
                else {
                    f[i][j] = getMax(f[i - 1][j], f[i - 1][j - c[i]] + v[i]);//转移方程式
                }
                System.out.print(f[i][j] + " ");
            }
        }
        for (int i = 0; i < f.length; i++) {
            System.out.println();
            for (int j = 0; j < f[i].length; j++) {
                System.out.print(f[i][j]);
            }
        }
    }

    private static int getMax(int a, int b) {
        return a > b ? a : b;
    }

}