python实现常见算法

1、o-1背包

代码实现

class Goods:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value
        self.priceRitio = weight/value

def GetMaxValue():
    value = 0
    weight = 30
    weightOfCurrent = 0
    goods = [Goods(4, 3), Goods(2, 8), Goods(9, 18), Goods(5, 6), Goods(5, 8), Goods(8, 20), Goods(5, 5), Goods(4, 6),
             Goods(5, 7), Goods(5, 15)]
    goods.sort(key=lambda Goods: Goods.priceRitio)    #按照重量/价值从小到大排序

    for i in goods:
        if weightOfCurrent+i.weight <= weight:       #从小到大选择
            value += i.value
            weightOfCurrent += i.weight
        else:
            break

    return value


if __name__ == "__main__":
        print(GetMaxValue())

2、会议安排

  

代码实现：
class Meeting:
    def __init__(self, id, startTime, endTime):
        self.id = id
        self.startTime = startTime
        self.endTime = endTime

def GetMaxMeetingNum():
    meetings = [Meeting(1,3,6), Meeting(2,1,4), Meeting(3,5,7), Meeting(4,2,5), Meeting(5,5,9),
                Meeting(6,3,8), Meeting(7,8,11), Meeting(8,6,10), Meeting(9,8,12), Meeting(10,12,14)]
    meetings.sort(key=lambda Meeting:Meeting.endTime)    #按照结束时间进行排序

    lastTime = meetings[0].endTime
    maxMeetNum = 1
    meetIdList = []
    meetIdList.append(meetings[0].id)
    for i in range(1, len(meetings)):
        if lastTime <= meetings[i].startTime:    #开始时间大于之前会议的最晚结束时间
            maxMeetNum += 1
            lastTime = meetings[i].endTime
            meetIdList.append(meetings[i].id)

    return maxMeetNum, meetIdList



if __name__ == "__main__":
    maxMeet, meetList = GetMaxMeetingNum()
    print("maxMeet is ", maxMeet)
    print("meetList is ", meetList)

3、二分查找 

def BinarySearch(n, nums, target):
    low = 0
    high = n - 1
    while low <= high:
        middle = int((low+high)/2)
        if nums[middle] == target:
            return middle
        elif nums[middle] > target:
            high = middle-1
        elif nums[middle] < target:
            low = middle+1
    return -1



if __name__ == "__main__":
    nums = [5, 8, 15, 17, 25, 30, 34, 39, 45, 52, 60]
    length = len(nums)
    print(BinarySearch(length, nums, 17))