猫史档案馆

算法（Algorithm）

是指解题方喵而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

 

一个准确定义的算法必须具备以下特征和性质：

有穷性（Finiteness）算法的有穷性是指算法必须能在执行有限个步骤之后终止。

确切性 (Definiteness) 算法的每一步骤必须有确切的定义；

输入项(Input)一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

输出项(Output)一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

可行性(Effectiveness)算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称为有效性）。

 

 

动态规划（Dynamic Programming，DP）

是求解问题的一种算法。

 

简单的说，动态规划将问题分成很多层子问题，对子问题分别求解，然后再将每个子问题所得的结果转移到其上一层子问题，得到该层子问题的答案并不断转移，最终得到最优解。

 

下面给出动态规划的相关概念及其定义。

阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。

状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以主观意志为转移，也称为不可控因素。

无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。

决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。

策略：由每个阶段的决策组成的序列称为策略。

允许策略集合中达到最优效果的策略称为最优策略。

 

给定k阶段状态变量x(k)的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么可以把这一关系看成(x(k)，u(k))与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程。

 

同样，动态规划也有其使用条件。

1.最优化原理（或称为：最优子结构性质）一个最优化策略的子策略总是最优的。

2.无后效性 一个状态之前的状态只能通过当前状态来影响之后的状态，不能直接影响。

3、子问题的重叠性  

为了更好的理解，我们引用一个经典的故事：国王挖金矿

这个故事网上随便一搜都能找到，我就不再赘述了。

我相信大家都了这个故事后能对攻台规划的基本思想有一个了解。

 

 

 

最长上升子序列（Longest Increasing Subsequence，LIS）

 

 

给定一个数列，在其中挑选出一些数（顺序不变），使任意相邻两数中，前一个数比后一个数小。求最多能选出多少个这样的数。

 

让我们分析一下这道题。

这是一道最经典也是最入门的DP题。

 

我们用一个数组a来存储数列，dp[i]来存储到第 i 个数为止的最长上升子序列。

int a[105],dp[105],maxn,n,i,j; 

 

初始化：因为每个数都是一个数列，所以答案至少是1.我们把dp[i]初始化为每个元素都是1

	for(i=0;i<105;i++)dp[i]=1;

 

然后就是求解过程了。

 

定义两个变量 i , j 。 i 从1遍历到n， j 从1遍历到 i - 1 .

	for(i=0;i<n;i++)
	    for(j=0;j<i;j++)

 如果i>j，表示扫描到新的一个数 j，它比 i 小。因此此时我们有两种选择：

1.在dp[j]的基础上加上第 i 个数

2.保留原先子序列，即dp[i]不变

我们只需在两者间选则更大的一个就行了。

 

以序列1,2,4,3,5为例，下面是图示过程（A集合就是a[i]，B集合就是dp[i]）。

 

经过上面的分析，我们得到状态转移方程如下：

	        if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);

 

那么如何输出答案呢？首先不能只输出包含最后一个元素的最长上升子序列，因为不一定是最优的。

这很好理解，比如4,5,6,1,。很显然，dp[4]是包含最后一个元素的最长上升子序列，但不是最优解。

因此我们定义变量maxn，依次扫描，如果有比maxn大的就更新maxn的值：

	for(i=0;i<n;i++)maxn=max(dp[i],maxn);

 

最后套上框架

#include<bits/stdc++.h>
using namespace std;
int main(){

    return 0;
}

 

这个代码就不难写出来了。

 

Code：

#include<bits/stdc++.h>
using namespace std;
int a[105],dp[105],maxn,n,i,j; 
int main(){
	for(i=0;i<105;i++)dp[i]=1;
	cin>>n;
	for(i=0;i<n;i++)cin>>a[i];
	for(i=0;i<n;i++)
	    for(j=0;j<i;j++)
	        if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);
	for(i=0;i<n;i++)maxn=max(dp[i],maxn);
	cout<<maxn;
	return 0;
}

 

 

 

 

01背包问题

 

 

01背包问题也是一类很经典并且简单的动态规划问题。

比如以下这个题目背景，就是一个标准的01背包问题。

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是喵药的山洞里对他说：“孩子，这个山洞里有一些不同的喵药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些喵药。如果你是一个聪明的孩子，你应该可以让采到的喵药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

 

说白了就是给你一个容量为t的背包和n件价值为v[i],体积为w[i]的物品（每件物品只能装一次），让你编程计算背包装下的物品价值最多是多少。

 

首先我们引入一个概念：设f[i]表示容量为i的背包能获得的价值最多是多少。那么，f[0]很明显是0，因为一件物品都装不下。而我们要求的就是当容量为t时可获得的最大价值，也就是f[t]。

  然后我们如何求f[i]可获得的价值？

 

我们都知道，只有背包剩余的容量大于一件物品时，才能装得下这件物品，获得这件物品的价值。那么我们就可以从每件物品出发：

 

for(int i=1;i<=n;i++){ } 

 

然后我们利用上面说的性质，枚举可以装得下第i件物品的剩余容量（f[i]）：

 

for(int i=1;i<=n;i++){ for(int j=t;j>=w[i];j--){ //t为背包总容量 } } 

 

为什么要从t开始枚举呢？

因为我们的每个物品只能放一次，而f[j]要靠f[j-w[j]]的价值求出来，如果我们先枚举f[j]再枚举f[j]以后的内容，就会被f[j]影响到，也就相当于第i件物品放了两次或以上（这涉及到完全背包问题，需要了解的可以去百度一下，或者做一下P1616）。所以我们从t开始枚举，以免影响到之前的f[i]。

  然后我们就可以通过动规的性质（不会影响到枚举过的内容）来求f[t]了。

 

由于不会影响到之前枚举过的内容，所以我们可以放心的贪心：

 

for(int i=1;i<=n;i++){ for(int j=t;j>=w[i];j--){ f[j]=max(f[j-w[i]]喵[i],f[j]); //w[i]是第i件物品的体积，v[i]是第i件物品的价值。 } } 

 

由于每件物品只能放一次，所以只有两个选择：放和不放（这也是0/1背包名字的来源）。

不放的话，f[j]还是f[j]，没有任何变化；

放的话，背包的容量就少了w[i]，只能获得f[j-w[i]]喵[i]的价值。

这两者的最大值，就是我们要求的f[j]。

最后的答案就是容量为t时获得的最大价值，也就是f[t]。

 

代码如下：

#include<iostream>
#include<cmath>
using namespace std;
int f[1001],n,t,v[101],w[101];
int main(){
	cin>>t>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++){ //t为背包总容量
		for(int j=t;j>=w[i];j--) {
            f[j]=max(f[j-w[i]]喵[i], f[j]);//w[i]是第i件物品的体积，v[i]是第i件物品的价值。
        }
	}
	cout<<f[t];
	return 0;
}

 

 

 

完全背包

 

 

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。　　

 

根据第i种物品放多少件进行决策，状态转移方程不难写出来。

 

F[i-1][j-K*C[i]]+K*W[i]表示前i-1种物品中选取若干件物品放入剩余空间为j-K*C[i]的背包中所能得到的最大价值加上k件第i种物品；

设物品种数为N，背包容量为V，第i种物品体积为C[i]，第i种物品价值为W[i]。

与01背包相同，完全背包也需要求出NV个状态F[i][j]。但是完全背包求F[i][j]时需要对k分别取0,…，j/C[i]求最大F[i][j]值。

这样代码应该是三层循环（物品数量，物品种类，背包大小这三个循环）

 

很明显，这样一般情况下会超时，需要转化成时间复杂度比较低的在进行求解。

 

经过思考可以想到完全背包可以转化为01背包：

因为同种物品可以多次选取，那么第i种物品最多可以选取V/C[i]件价值不变的物品，然后就转化为01背包问题。如果把第i种物品拆成体积为C[i]×2k价值W[i]×2k的物品，其中满足C[i]×2k≤V。即设F[i][j]表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。那么对于第i种物品的出现，我们对第i种物品放不放入背包进行决策。如果不放那么F[i][j]=F[i-1][j]；如果确定放，背包中应该出现至少一件第i种物品，所以F[i][j]种至少应该出现一件第i种物品,即F[i][j]=F[i][j-C[i]]+W[i]。为什么会是F[i][j-C[i]]+W[i]？因为F[i][j-C[i]]里面可能有第i种物品，也可能没有第i种物品。我们要确保F[i][j]至少有一件第i件物品，所以要预留C[i]的空间来存放一件第i种物品。

　　

状态方程为：

 

0-1背包和完全背包的不同：

　　从二维数组上区别0-1背包和完全背包也就是状态转移方程就差别在放第i中物品时，完全背包在选择放这个物品时，最优解是F[i][j-c[i]]+w[i]即画表格中同行的那一个，而0-1背包比较的是F[i-1][j-c[i]]+w[i]，上一行的那一个。

　　从一维数组上区别0-1背包和完全背包差别就在循环顺序上，0-1背包必须逆序，因为这样保证了不会重复选择已经选择的物品，而完全背包是顺序，顺序会覆盖以前的状态，所以存在选择多次的情况，也符合完全背包的题意。状态转移方程都为F[i] = max(F[i],dp[F-c[i]]喵[i])。

 

 

完全背包代码

 

#include<cstdio>
#include<algorithm>
using namespace std;
int w[300],c[300],f[300010];
int V,n;
int main()
{
    scanf("%d%d",&V,&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&w[i],&c[i]);
    }
    for(int i=1; i<=n; i++)
        for(int j=w[i]; j<=V; j++)//注意此处，与0-1背包不同，这里为顺序，0-1背包为逆序
            f[j]=max(f[j],f[j-w[i]]+c[i]);
    printf("max=%d\n",f[V]);
    return 0;
}

 

 

 

多重背包

 

 

有N种物品和一个容量为T的背包，第i种物品最多有M[i]件可用，价值为P[i]，体积为V[i]，求解：选哪些物品放入背包，可以使得这些物品的价值最大，并且体积总和不超过背包容量。

对比一下完全背包，其实只是多了一个限制条件，完全背包问题中，物品可以选择任意多件，只要你装得下，装多少件都行。

但多重背包就不一样了，每种物品都有指定的数量限制，所以不是你想装，就能一直装的。

举个栗子：有A、B、C三种物品，相应的数量、价格和占用空间如下图：

下面给出状态转移方程（话说这不打LeTeX还真不行啊）

 

代码如下

#include <bits/stdc++.h>
using namespace std;
struct E
{
    int w;  //体积
    int v;  //重量
} lis[2001]; 
int dp[101];
int main()
{
    int T,n,m;
    int p,h,k;
    int i,j;
    int index,c;
    scanf("%d%d",&n,&m);                //n表示容量，m表示种类
    index = 0;  //拆分后物品总数
    for( i=1; i<=m; i++)
    {
        c = 1;
        scanf("%d%d%d",&p,&h,&k);       //p表示价格，h表示重量，k表示大米袋数。
        while( k-c>0)
        {
            k -= c;
            lis[++index].w = c*p;
            lis[index].v = c*h;
            c *= 2;
        }
        lis[++index].w = p*k;  //补充不足指数的差值
        lis[index].v = h*k;
    }
    for( i=0; i<=n; i++) dp[i]=0;
    for( i=1; i<=index; i++)   //对拆分后的物品进行0-1背包
    {
        for( j=n; j>=lis[i].w; j--)
            dp[j] = max( dp[j],dp[j-lis[i].w]+lis[i].v);
    }
        printf("%d\n",dp[n]);
    return 0;
}