算法相关

Posted on

算法记录

4.动态规划: i个物品，价格ai，收益bi，预算m，单次购买最大收益？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def t1():
    res = [[0]*(m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if j < A[i-1]:
                res[i][j] = res[i-1][j]
            else:
                res[i][j] = max(res[i-1][j], res[i-1][j-A[i-1]]+V[i-1])
    return res[-1][-1]
def t2():
    res = [0] * (m+1)
    for i in range(1, n+1):
        for j in range(m, 0, -1): # 必须逆序
            if A[i-1]<=j:
                res[j] = max(res[j], res[j-A[i-1]]+V[i-1])
    return res[-1]

5.给定整数数组nums，给定元素个数n，求子数组？

解法1：常规遍历

1
2
3
4
5
6
7
8
9
def subsets(nums):
    output = [[]]
    for num in nums:
        for cur in output.copy():
            ext = cur + [num]
            output.append(ext)
        # output += [cur + [num] for cur in output] # 简化
    return output
print(subsets([1,2,3,4,5]))

解法2: 位运算

1
2
3
4
5
6
7
8
9
def subsets(nums):
    output = []
    for i in range(2**len(nums)):
        sub = []
        for j in range(len(nums)):
            if (i >> j) % 2 == 1: # 当前位1取0不取
                sub.append(nums[j])
        output.append(sub)
    return output

解法3: 回溯

1
2
3
4
5
6
7
8
9
10
def subsets(nums):
    res = []
    n = len(nums)
    def helper(i, tmp):
        res.append(tmp)
        for j in range(i, n):
            helper(j + 1, tmp+[nums[j]])
    helper(0, [])
    return res
print(subsets([1,2,3,4]))

变种1: 求子数组和可被整除

解法1：拆分&查找

1
2
3
4
5
print(sum(map(lambda x:x%m==0, subsets(nums)[1:])))
# 优化:拆分&查找
mid = (len(nums)+1)/2
nums1 = nums[:mid]
nums1 = nums[mid:]