笔试时候遇到的动态规划问题比较多，背包问题比较有代表性，所以自己手动全部实现一遍，加深转移方程的推导与实现的记忆。下面依次介绍01背包（每种物品只有1个）、完全背包（每种物品有无限个）、多重背包（每种物品各有限制）

01背包

背包容量为cubage，物品种类为cate种，物品i花费为cost[i]，价值为value[i]
对于二维数组dp[i][j]表示容积为j放入前i种物品的最优解（价值最大值）
//代码中注释都说的比较详细，就不展开了，中途会插入一些参考链接

1
2
3
4
5
6
7
8
9
10
11
12
13

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int cubage = sc.nextInt();
	int cate = sc.nextInt(),i=1;
	int[] value = new int[cate+1];
	int[] cost = new int[cate+1];
	while(i<=cate){
		cost[i]=sc.nextInt();
		value[i]=sc.nextInt();
		i++;
	}
	parse01Normal(value,cost,cubage,cate);
}

查看更多

体系机构

查看更多

问题描述
对于母串X={x₁,x₂,⋯,x_m}, Y={y₁,y₂,⋯,y_n}, 求LCS与最长公共子串。
假设 Z_k={z₁,z₂,⋯,z_k} 是 X 与 Y 的 LCS， 可以观察到

• 如果x_m=y_n，则 z_k=x_m=y_n，有 Z_k−1 是 X_m−1、Y_n-1 的 LCS；
• 如果x_m≠y_n ，则 Z_k 是 X_m 与 Y_n−1 的LCS，或者 X_m−1 与 Y_n 的 LCS

查看更多

JDK中的排序算法

Java 数组方法中的Sort方法(1.7开始多了基于TimSort的parallelSort，是一种优化过的归并排序，适合多核对大数组切分然后归并）其实包含三种排序算法，当待排序数组长度小于47时，采用插入排序，小于286时采用快速排序，大于286则采用归并排序，由此可见三种排序在不同数据规模下的效率。下面以升序为例介绍三种算法。

查看更多

本文转载自Litten，已获作者授权。

1. 前言

对于一张网页，我们往往希望它是结构良好，内容清晰的，这样搜索引擎才能准确地认知它。
而反过来，又有一些情景，我们不希望内容能被轻易获取，比方说电商网站的交易额，教育网站的题目等。因为这些内容，往往是一个产品的生命线，必须做到有效地保护。这就是爬虫与反爬虫这一话题的由来。
因为自己写过些爬虫，也见过一些非常让人头疼的网站，但是自己并非专业写爬虫，分析也远不如这一篇博客里面写得那么详细和专业，所以遇到这篇好文章，非常感慨，向原作者申请转载。

查看更多

　　上一次正儿八经的写博客还是本科毕设的时候，那时候各种查资料，觉得很多东西需要自己整理到一起，方便后面查阅，而不用一页页翻收藏夹。但是后来写博客就太懒了，因为多数时候我都是遇到问题或者好奇什么技术才回去翻别人的博客，等自己看完之后其实很少继续思考，所以自己写博客的时候往往就几句话，然后贴一堆别人文章的链接。

查看更多

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

查看更多