近期事情多，且老师讲动态规划讲得云里雾里。。于是又没有跟上进度，菜鸡终于要来填坑了。
动态规划
动态规划和分治法有些相像，都是把一个问题分成了很多子问题来求解，但是不同的是动态规划会记忆之前解决的子问题的结果，避免了重复计算。判断一个问题是否能用动态规划求解，要看它是否能划分成合适的子问题，然后写出递推关系式。
动态规划得到的解一定是最优解。
01背包问题

（1）问题描述：

现有n件物品，每件都有对应的重量（w）和价值（v），有一个给定容量（C）的背包，怎么样才能在背包里装入具有最大价值总和的东西？

具体例子：



（2）问题分析：

突然想到之前看数模书的时候提到的一种思路——引入0-1变量，化为整数规划问题。

模型建立：已知n件物品的重量为W1~Wn ，价值为V1 ~Vn，用X1 ~Xn来表示是否选了这件物品放入背包，Xi为0或1。

决策目标即为：MAX(V1X1+V2X2+…+VnXn)

约束条件即为：(W1X1+W2X2+…+WnXn) ≦ C

抖机灵用lingo求了下解。。



好了言归正传。。

（3）寻找子问题和建立递推关系式

这里采用自底向上的思路

定义子问题：在前i个物品里面挑选总重量不大于W（W<=C）的物品，记最优值为M(i, W)，则对于第i个物品来说就有两种情况：

①Wi>W，装不下了，则M(i, W)=M(i-1, W)；

②Wi<=W，那么就要选择装不装，则M(i, W)=max{M(i-1, W) , M(i-1, W-Wi)+Vi}

M(i-1, W-Wi)即为第i个物品装入之前的最优值，结果是装了第i个物品。

接下来就是初始化的问题了，还是看源代码吧。

（4）源代码：
public class FindMax {	
	public static void main(String[] args){
		int capacity=11;
		int item_num=5;
		int[][] M = new int[item_num+1][capacity+1];
		int[] w={0,1,2,5,6,7};
		int[] v={0,1,6,18,22,28};
		int i,j;
		for(i=0;i<=capacity;i++){
			M[0][i]=0;
		}
		for(j=0;j<=item_num;j++){
			M[j][0]=0;
		}
		for(i=1;i<=item_num;i++){
			for(j=1;j<=capacity;j++){
				if(w[i]>j){
					M[i][j]=M[i-1][j];
				}
				else{
					M[i][j]=Math.max(M[i-1][j], M[i-1][j-w[i]]+v[i]);
				}
			}
		}
		for(i=0;i<=item_num;i++){
			for(j=0;j<=capacity;j++){
				System.out.print(M[i][j]+ "\t");
			}
			System.out.println("");
		}
	}
}

结果截图如下：



最优解为40，那么怎么知道是哪几件物品被选中了呢？我们要从表的右下角往回看，M(5, 11)=M(4, 11)=40且M(4,11)不等于M[3,11]，说明选了4号物品；减去4号物品的重量40-22=18，M(3, 5)=18且M(3,5)不等于M(2, 5)且M(3,5)=M(4,5)=M(5,5)，说明第三件物品被选择了，减去三号物品的重量40-22-18=0；说明被选中的就是3号和4号。
今天就写到这里吧。

动态规划求解 01背包问题 java语言
1、求最优解及最优解路径

package G.C;
import java.util.*;
public class 动态规划01背包 {
static int w[] = {0, 2,3,4,5 };//商品的体积2、3、4、5
static int v[] = {0,3,4,5,6 };//商品的价值3、4、5、6
static int bagV = 8;	
static int vBagv[][]= new int [5][9];
static int maxV = 0 ;
static Set<Integer> haveAdd = new HashSet<>();

public static void main(String[] args) {
	

	for(int i=1;i<=4;i++){
		for(int j=1;j<=8;j++){
			if(j<w[i]){//不装入
				vBagv[i][j] = vBagv[i-1][j];
			}else{ //装入
				vBagv[i][j] = Math.max( vBagv[i-1][j], vBagv[i-1][j-w[i]]+v[i]);
			}
			if(vBagv[i][j]>maxV){
				maxV = vBagv[i][j];
			}
		}
	}
		
	//求加入的商品体积
	findAddLj(4,8);
	
	System.out.print(maxV);
	System.out.print(haveAdd.toString());
}

private static void findAddLj(int i,int j) {
	if(i>=1){
		if(vBagv[i][j]  == vBagv[i-1][j] ){ //没加入 第 i个商品没加入
			findAddLj(i-1,j);
		}else{//
			if(j>=w[i]&&vBagv[i][j]== vBagv[i-1][j-w[i]]+v[i] ){
				haveAdd.add(w[i]);// 第 i个商品没加入
				findAddLj(i-1,j-w[i]);
			}
		}
	}
	}

}

求解过程可参考 博客：

https://blog.csdn.net/qq_38410730/article/details/81667885

用动态规划求解01背包问题
题目描述

给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
输入

输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。

以后N行每行两个数Wi和Vi,表示物品的重量和价值
输出

输出1行，包含一个整数，表示最大价值。
样例输入

3  5

2 3

3 5

4 7
样例输出

8
这里使用二维数组解决，会更加通俗易懂的。

其实可以使用一维数组进行空间优化。
package oj;
import java.util.Scanner;

/**
 * @author JMChen
 * @date 2020/4/24
 */
public class ZeroOneBackpack {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num, weight;

        //求的是dp[num][weight]
        num = sc.nextInt();
        weight = sc.nextInt();

        int i, j;

		//假设第一个为0，方便下标计算
        int[] p = new int[num + 1];
        int[] w = new int[num + 1];
        int[][] table = new int[num + 1][weight + 1];


        // 默认下标为0的取值为0,方便计算
        for (i = 1; i <= num; i++) {
            w[i] = sc.nextInt();            //每个东西的重量
            p[i] = sc.nextInt();            //每个东西的价值
        }

        //看成对d[i][j]的赋值
        //dp转移方程从d[1][1] 推出dp[num][weight]的值
        for (i = 1; i <= num; i++)
            for (j = 1; j <= weight; j++) {
                if (j < w[i]) table[i][j] = table[i - 1][j];
                else table[i][j] = Math.max(table[i - 1][j], table[i - 1][js - w[i]] + p[i]);
            }
//可以将整个表打出来看看
//        for(i=0;i<=num;i++)
//        {
//            for(j=0;j<=weight;j++)
//                System.out.print(table[i][j]+ "  ");
//            System.out.println();
//        }

        System.out.print(table[num][weight]);
    }
}


关键思路：转移方程

dp[i][j] = max(dp[i−1,j], dp[i−1][j−w[i]] + v[i])

01背包问题：给定N中物品和一个背包，物品i的重量是Wi,其价值位Vi，背包的容量为C。问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大？每件物品可以选择装或者不装。
i代表前i个物品（包括i），j表示背包重量，f(i, j)表示从前i个物品中选取到总重量不超过j的最大价值。
如果wi > j: f(i, j) = f(i-1, j) 否则f(i, j) = max（f(i-1, j), f(i-1, j-wi) +vi）。
假设山洞里共有a,b,c,d ,e这5件宝物（不是5种宝物），它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包, 怎么装背包，可以才能带走最多的财富。


def package_max_value(weight, value, package_volume):
    if len(weight) <= 0 or len(value) <= 0 or len(weight) != len(value):
        return []
    res = [[0 for i in range(package_volume)] for i in range(len(value))]
    for j in range(package_volume):
        if j < weight[0]:
            res[0][j] = 0
        else:
            res[0][j] = value[0]

    for i in range(1, len(value)):
        for j in range(package_volume):
            if j < weight[i]:
                res[i][j] = res[i-1][j]
            else:
                res[i][j] = max(res[i-1][j], res[i-1][j-weight[i]] + value[i]) 

    return res

weight = [2,2,6,5,4]
value = [6,3,5,4,6]
package_volume = 10
print(package_max_value(weight, value, package_volume))
运行结果如下。




其中遇到二维数组赋值问题，res = [[0]* package_volume]*len(value)，其中package_volume = 10, len(value)  = 5,生成二维数组后赋值操作，譬如res[1][2] = 20，结果每行的第三个元素变为20。原来是python中[array]*num中是创建了num个指向[array]的引用，一旦[array]改变，每行都改变。
正确创建二维数组的方式是[[0 for i in range(row)] for j in range(column)]
备注：一维数组通过[0]*5创建，是确实创建了5个元素，改变其中一个不影响其他元素。这么看来，*的操作是单个元素进行申请内容，而对list元素只做引用，只能deepcopy才可以真正复制list中的list元素。


最长递增子序列：最长递增子序列（Longest Increasing Subsequence）是指找到一个给定序列的最长子序列的长度，使得子序列中的所有元素单调递增。

例如：[3,5,7,1,2,8,4]的LIS是[3,5,7,8]，长度为 4。

def longest_ascending_sub(src):
    if len(src) <= 1:
        return src
    res = [1 for i in range(len(src))]
    subsequence = [[ele] for ele in src]
    for i in range(len(src)):
        for j in range(i):
            if src[i] >= src[j] and res[j] + 1 > res[i]:
                res[i] = res[j] + 1
                subsequence[i] = subsequence[j] + [src[i]]
    
    return res, subsequence

src = [3,5,7,1,2,8,4]
a, b = longest_ascending_sub(src)
print('---每个位置最长递增序列的长度----')
print(a)
print('---每个位置最长递增序列的元素----')
print(b)
print('---最长数据为---\n%s'%len(b[a.index(max(a))]))
运行结果如下。