dp182
昨天做了爱奇艺的内推笔试，编程题又出现了动态规划问题，感觉动态规划出现的概率好大，需要加强下。这里借用背包问题开始我们的学习。
背包问题的经典讲解可以参见背包问题九讲，此外我在刷题的过程中发现还发现了背包六问。
0 1 背包
最经典的 01 背包问题可以描述为：
有n个物品，每个物品的重量为w[i]，每个物品的价值为v[i]。现在有一个背包，它所能容纳的重量为W，问：当你面对这么多有价值的物品时，你的背包所能带走的最大价值是多少？我们用c[i][w]表示处理到第i 个物品时背包容量为w下所能装下的最大价值。关键的状态转移方程如下：
伪代码如下：
优化空间复杂度
以上方法的时间和空间复杂度均为O(Wn)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O(W)。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i = 1..n，每次算出来二维数组 c[i][0..W] 的所有值。那么，如果只用一个数
组c[0..W]，能不能保证第 i 次循环结束后 c[w] 中表示的就是我们定义的状态 c[i][w] 呢？ c[i][w] 是由 c[i - 1][w] 和 c[i-1][w - c[i]] 两个
子问题递推而来，能否保证在推 c[i][w] 时（也即在第 i 次主循环中推 c[w] 时）能够得到 c[i - 1][w] 和 c[i - 1][w - c[i]] 的值呢？事实
上，这要求在每次主循环中我们以 w=W..0的顺序推 c[w]，这样才能保证推 c[w] 时 c[w - c[i]] 保存的是状态 c[i - 1][w - c[i]] 的值。伪
代码如下：
for i = 1..n
for w = W..0
c[w] = max{c[w], c[w - w[i]] + v[i]};其中的 c[v] = max{c[w], c[w - c[i]]}一句恰就相当于我们的转移方程 c[i][w] = max{c[i - 1][w], c[i - 1][w - c[i]]}，因为现在的 c[w - c[i]]就
相当于原来的 c[i - 1][w - c[i]]。如果将 v 的循环顺序从上面的逆序改成顺序的话，那么则成了 c[i][w] 由 c[i][w - c[i]] 推知，与本题意不
符，但它却是完全背包问题最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。
过程ZeroOnePack，表示处理一件01背包中的物品，两个参数weight、value分别表明这件物品的重量和价值。
procedure ZeroOnePack(weight, value)
for w = W..weight
c[w] = max{c[w], c[w - weight] + value}注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成 w = W..0是为了在程序中体现每个状态都按照方程求解
了，避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了，就可以加入优化。费用为cost的物品不会影响状态c[0..weight - 1]，这是显然的。
有了这个过程以后，01背包问题的伪代码就可以这样写：
for i=1..N
ZeroOnePack(w[i], v[i]);完全背包
基本思路
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令 c[i][w] 表示前 i 种物品恰放入一个容量为w的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：
c[i][w] = max{c[i - 1][w - k * w[i]] + k * v[i] | 0 <= k * w[i] <= w}
这跟01背包问题一样有O(Wn)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态 c[i][w] 的时间是O(w / w[i])，总的复杂度可以认为是O(W * Σ(W / w[i]))，是比较大的。
将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。
O(Wn)的算法
这个算法使用一维数组，先看伪代码：
for i = 1..n
for w = 0..W
c[w]=max{c[w], c[w - w[i]] + v[i]}你会发现，这个伪代码与上面01背包的伪代码只有w的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么01背包中要
按照 w = W..0 的逆序来循环。这是因为要保证第 i 次循环中的状态 c[i][w] 是由状态 c[i - 1][w - w[i]] 递推而来。换句话说，这正是为
了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第 i 件物品的子结果
c[i - 1][w - w[i]] 。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物品”这种策略时，却正需要一个可
能已选入第 i 种物品的子结果 c[i][w - w[i]]，所以就可以并且必须采用 w = 0..W的顺序循环。这就是这个简单的程序为何成立的道
理。
最后抽象出处理一件完全背包类物品的过程伪代码：
procedure CompletePack(weight, value)
for w = weight..W
c[w] = max{c[w], c[w - weight] + value}多重背包
可以参见：多重背包
先在这挖个坑，以后遇到了再来。。
下面实战一下背包问题，题目均来自 lintcode 。
1、Backpack
题目叙述：
Given n items with size Ai, an integer m denotes the size of a backpack.
How full you can fill this backpack?
Example
If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5],
so that the max size we can fill this backpack is 10. If the backpack size is 12.
we can select [2, 3, 7] so that we can fulfill the backpack.
You function should return the max size we can fill in the given backpack.题目分析：
该问题是 01 背包问题的简化版。
依照题目我们可以得到状态转换方程：
res[i][j] = max{res[i - 1][j - w[i]] + w[i], res[i - 1][j]}同理我们也可以按照 01背包的空间复杂度优化方法优化如下：
res[j] = max{res[j - w[i]] + w[i], res[j]}代码如下：
class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
int backPack(int m, vector<int> A) {
// write your code here
int n = A.size(), i, j;
vector<int> res(m + 1);
for(i = 0; i < n; ++i)
{
for(j = m; j >= A[i]; --j)
{
res[j] = max(res[j - A[i]] + A[i], res[j]);
}
}
return res[m];
}
};2、Backpack II
题目描述：
Given n items with size Ai and value Vi, and a backpack with size m.
What's the maximum value can you put into the backpack?
Example
Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.题目分析：
该题目就是我们的 01 背包问题。
代码如下：
class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param A & V: Given n items with size A[i] and value V[i]
* @return: The maximum value
*/
int backPackII(int m, vector<int> A, vector<int> V) {
// write your code here
int n = A.size(), i, j;
vector<int> res(m + 1);
for(i = 0; i < n; ++i)
{
for(j = m; j >= A[i]; --j)
{
res[j] = max(res[j - A[i]] + V[i], res[j]);
}
}
return res[m];
}
};3、Backpack VI
题目描述：
Given an integer array nums with all positive numbers and no duplicates, find the number of
possible combinations that add up to a positive integer target.
Example
Given nums = [1, 2, 4], target = 4
The possible combination ways are:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]
return 6题目分析：
该问题是 重复选择+不同排列+装满可能性总数
这道题开始就把我给看晕了。。
代码如下：
class Solution {
public:
/**
* @param nums an integer array and all positive numbers, no duplicates
* @param target an integer
* @return an integer
*/
int backPackVI(vector<int>& nums, int target) {
// Write your code here
int n = nums.size(), i, j;
vector<int> res(target + 1);
res[0] = 1;
for(i = 1; i <= target; ++i)
{
for(j = 0; j < n; ++j)
{
if(nums[j] <= i)
{
res[i] += res[i - nums[j]];
}
}
}
return res[target];
}
};
后来看到一个比较好的解释：
假设用 res[i] 表示容量为 i 的时候，有多少种装的方法。
每次考虑把当前 nums[j] 的空间腾出来，然后装进去 nums[j] 。这样的话需要考虑 res[i - nums[j]] 有多少种方法，把这些方法加到当前的 res[i] 中去。
初始化res[0] = 1，因为假如 res[2] = 0，第一件物品 nums[0] = 2，那么根据上面所说，res[2] += res[0]，现在 res[2] 应该为2，因为
把第一件物品 2 放进去空包里也算一种方法。
相关阅读
https://ita.skanev.com/俄罗斯一位强者写的，但是目前只有1-11章节。
我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。排序算法大体可分为两种：一种是比较排序，时间复杂度O(
原文地址：http://www.wtoutiao.com/p/1fe9dPI.html各种滤波算法的比较数字滤波方法有很多种，每种方法有其不同的特点和使用范围。从
调用pycryptodome库中的Blowfish模块，实现加密解密#/usr/bin/python # -*- coding: utf-8 -*- from Crypto.Cipher import Blowfis
相关文章： 数据挖掘领域十大经典算法之—C4.5算法（超详细附代码） 数据挖掘领域十大经典算法之—K-Means算法（超详细附代码