算法实验(一)
in Algorithms with 0 comment

算法实验(一)

in Algorithms with 0 comment
快速排序与背包问题相关算法分析

快速排序

相关文章

普通快速排序

算法效率:

伪代码

对整个数组进行递归排序:

QUICKSORT(A,p,r)
if p < r:
    q = PARTITION(A,p,r);
    QUICKSORT(A,p,q-1);
    QUICKSORT(A,q+1,r); 

快速排序算法的关键是PARTITION过程,它对A[p..r]进行就地重排:

PARTITION(A,p,r)
x = A[r]
i = p-1
for j = p to r-1// A[j]是待比较的元素
  if A[j] ≤ r// 若A[j]比主元小
    i = i + 1 // i往后一位(符合,不用替换;不符合i就停在这个地方,等着j过来叫唤)
    exchange A[i] with A[j]//倘若A[j]比主元小,其实是不发生交换的。
exchange A[i+1] with A[r]
return i + 1

python代码

# coding=utf-8
import datetime
import sys   
sys.setrecursionlimit(1000000)
def SET_NUMBER():
    l = []
    for i in range(0,len(range(1,2000,2)[::-1])-1):
        l.append(range(1,2000,2)[::-1][i])
    return l
        
def PARTITION(A,p,r):
    x = A[r]
    i = p - 1
    for j in range(p,r):
        if A[j]<=x:
            i = i + 1
            A[i],A[j]=A[j],A[i]
    A[i+1],A[r] = A[r],A[i+1]
    return i+1


def QUICKSORT(A,p,r):
    if p >= r:
        return
    q = PARTITION(A,p,r)
    QUICKSORT(A,p,q-1)
    QUICKSORT(A,q+1,r)
    
if __name__ == '__main__':
    l = SET_NUMBER()
    time1 = datetime.datetime.now()
    QUICKSORT(l,0,len(l)-1)
    time2 = datetime.datetime.now()
    print(time2-time1)

随机快速排序

算法效率

我们已经知道,若输入本身已被排序,那么对于快排来说就糟了。那么如何避免这样的情况?一种方法时随机排列序列中的元素;另一种方法时随机地选择主元(pivot)。这便是随机化快速排序的思想,这种快排的好处是:其运行时间不依赖于输入序列的顺序。

经分析, 随机化快排的算法效率是$Θ(nlgn)$

伪代码

下面是分化(Partition)

Random_Partition(vector<T> &A,int p,int q)
    int i=rand()%(q-p)+p;  //此行与快排不同、加入随机数参数器
    Swap(A[i],A[p]);         //此行与快排不同、随机选取主元
    return Partition(A,p,q);//此次与快速排序一样

随机化快速排序

Random_Quick_Sort(vector<T> &A,int p,int q)
    if (p<q):
        int i=Random_Partition(A,p,q);
        Random_Quick_Sort(A,p,i-1);
        Random_Quick_Sort(A,i+1,q);

python代码

# coding=utf-8
import datetime
import random
def SET_NUMBER():
    l = []
    for i in range(0,len(range(1,2000,2)[::-1])-1):
        l.append(range(1,2000,2)[::-1][i])
    return l


def PARTITION(A,p,r):
    x = A[r]
    i = p - 1
    for j in range(p,r):
        if A[j]<=x:
            i = i + 1
            A[i],A[j]=A[j],A[i]
    A[i+1],A[r] = A[r],A[i+1]
    return i+1

def Random_Partition(A,p,r):
    i = random.randint(p, r) 
    A[i],A[p]=A[p],A[i]
    return PARTITION(A,p,r)

def QUICKSORT(A,p,r):
    if p >= r:
        return
    q = Random_Partition(A,p,r)
    QUICKSORT(A,p,q-1)
    QUICKSORT(A,q+1,r)
    
if __name__ == '__main__':
    l = SET_NUMBER()
    time1 = datetime.datetime.now()
    QUICKSORT(l,0,len(l)-1)
    time2 = datetime.datetime.now()
    print(time2-time1)

时间效率

分析性能差异

快速排序的平均时间复杂度为$O(nlogn)$,最坏时间时间可达到$O(n^2)$,最坏情况是当要排序的数列基本有序的时候。根据快速排序的工作原理我们知道,选取第一个或者最后一个元素作为主元,快速排序依次将数列分成两个数列,然后递归将分开的数列进行排序。

当把数列平均分成两个等长的数列时,效率是最高的,如果相差太大,效率就会降低。

我们通过使用随机化的快速排序随机的从数列中选取一个元素与第一个,或者最后一个元素交换,这样就会使得数列有序的概率降低。

所以随机快速排序平均速度是比快速排序要快的,但是因为随机排序需要有设置随机数+交换元素的时间,因此总时间上不如普通快速排序。

背包问题

相关文章

动态规划知识复习

基本步骤

若给定问题具有以下性质:

0-1背包问题

定义问题

问题:有n个物品,第i个物品价值为$v_i$,重量为$w_i$,其中$v_i$和$w_i$均为非负数,背包的容量为W,W为非负数。现需要考虑如何选择装入背包的物品,使装入背包的物品总价值最大。

该问题以形式化描述如下:


满足约束条件的任一集合(x1,x2,...,xn)是问题的一个可行解,问题的目标是要求问题的一个最优解。考虑一个实例,假设n=5,W=17, 每个物品的价值和重量如下表所示。可将物品1,2和5装入背包,背包未满,获得价值22,此时问题解为你(1,1,0,0,1)。也可以将物品4和5装入背包,背包装满,获得价值24,此时解为(0,0,0,1,1)。

按步骤求解问题

根据上述分析的最优解的结构递归地定义问题最优解。设c[i,w]表示背包剩余容量为w时,i个物品导致的最优解的总价值。
分为三种情况:

伪代码:

BOTTOM-UP-CUT-ROD(p,n)
let  r[0..n] be a new array
r[0]= 0
for  j = 1 to n
    q= -∞
    for  i = 1 to j
        q = max(q, p[i]+r[j-i])
    r[j]= q
return  r[n]

python代码

#coding:utf-8  
def bag(n,m,w,v):  
    res = [[0 for j in range(m+1)]for i in range(n+1)] #n+1 行,m+1列 值为0的矩阵  
    for i in range(1,n+1):  
        for j in range(1,m+1):  
            res[i][j] = res[i-1][j] #0->res[0][1]->res[1][1]  
            if j>=w[i-1] and res[i][j]<res[i-1][j-w[i-1]]+v[i-1]:#如果res[i-1][j]小于res[i-1][j-w[i-1]]+v[i-1],那么res[i][j]就等于res[i-1][j],否则就等于res[i-1][j-w[i-1]]+v[i-1]  
                res[i][j] = res[i-1][j-w[i-1]]+v[i-1]  
    return res  
  
def show(n,m,w,res):  
    print (u"最大值为%d"%res[n][m]) 
    x = [False for i in range(n)]  
    j = m  
    for  i in range(n,0,-1):  
        if res[i][j]!=res[i-1][j]:  
            x[i-1] = True  
            j-=w[i-1]  
    print (u"选择的物品为")  
    for i in range(n):  
        if x[i]:  
            print(u"第%d个"%(i+1))  
  
if __name__ == "__main__":  
    #n种物品,承重量为m,w物品的重量,v 物品的价值  
    n= 5  
    m = 17  
    w = [3,4,7,8,9] 
    v = [4,5,10,11,13]  
    res = bag(n,m,w,v)  
    show(n,m,w,res) 

部分背包问题

题目要求使用贪心算法

具体题目

假设背包可容纳50Kg的重量,物品信息如下:

物品 i重量(Kg)价值单位重量的价值
110606
2201005
3301204

伪代码

这个看起来就很简单,先装单价最高的1,剩下的地方装2,再剩下的地方装3
我也不知道怎么写伪代码,直接写python吧

C代码

#include <stdio.h>  
#include <algorithm>  
using namespace std;  
  
  
//物品结构体,包含两个属性,w表示重量,v表示价值  
struct Good{  
    int id;  
    double w;  
    double v;  
};  
  
//排序比较函数,以物品的价值/重量比值降序排序  
bool cmp(Good a, Good b){  
    if (a.v/a.w > b.v/b.w) {  
        return true;  
    }  
    return false;  
}  
  
//结构体数组,所有物品信息  
struct Good goods[] = {{1,10,12},{2,9,9},{3,11,7},{4,12,9},{5,6,8},{6,3,4}};  
  
  
//背包总重量  
double totalW = 30;  
  
int main()  
{  
    //以物品的价值/重量比值降序排序  
    sort(goods,goods+6,cmp);  
    double leftW = totalW;  
    int totalV = 0;  
      
    //遍历排好序的物品数组  
    for (int i=0; i<6; i++) {  
        //如果当前背包所能承受的重量大于i物品的总量  
        //那么把i物品全部放进去  
        if (leftW >= goods[i].w) {  
            leftW -= goods[i].w;  
            totalV += goods[i].v;  
            printf("choose good[id = %d], %.1f weight,make %.1f value\n",goods[i].id,goods[i].w,goods[i].v);  
              
        //如果不能,那么取当前背包所能承受重量的相应数量物品  
        //当然价值也得按照比例来  
        }else {  
            totalV += leftW/goods[i].w * goods[i].v;  
            leftW = 0;  
            printf("choose good[id = %d], %.1f weight,make %.1f value\n",goods[i].id,leftW,leftW/goods[i].w * goods[i].v);  
            break;  
        }  
    }  
      
    printf("max total value:%d\n",totalV);  
    return 0;  
}  
Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号