头像

shiqumi

RUC


访客:6244

离线:2个月前


活动打卡代码 AcWing 4. 多重背包问题

shiqumi
3个月前
# if __name__ == '__main__':
#     n, m = map(int, input().split())
#     v = [0 for i in range(n + 1)]; w = [0 for i in range(n + 1)]; s = [0 for i in range(n + 1)]
#     f = [[0 for j in range(m + 1)] for i in range(n + 1)]

#     for i in range(1, n + 1):
#         v[i], w[i], s[i] = list(map(int, input().split()))
    # # 朴素做法(TLE)
    # for i in range(1, n + 1):
    #     for j in range(0, m + 1):
    #         k = 0
    #         while k <= s[i] and k * v[i] <= j:
    #             f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i])
    #         k += 1

    # print(f[n][m])

if __name__ == '__main__':
    n, m = map(int, input().split())
    f = [0 for i in range(m + 1)]
    newgood = []
    # 二进制处理,一边输入每种物品的信息,一边将si个物品i转化为数量更少的新商品
    for i in range(1, n + 1):
        v, w, s = list(map(int, input().split()))
        k = 1
        while k <= s:
            s -= k
            newgood.append([k*v, k*w])
            k *= 2
        if s > 0:
            newgood.append([s*v, s*w])


    # 01背包问题
    for t in newgood:
        j = m
        while j >= t[0]:
            f[j] = max(f[j], f[j - t[0]] + t[1])
            j -= 1
    print(f[m])





活动打卡代码 AcWing 5. 多重背包问题 II

shiqumi
3个月前
# if __name__ == '__main__':
#     n, m = map(int, input().split())
#     v = [0 for i in range(n + 1)]; w = [0 for i in range(n + 1)]; s = [0 for i in range(n + 1)]
#     f = [[0 for j in range(m + 1)] for i in range(n + 1)]

#     for i in range(1, n + 1):
#         v[i], w[i], s[i] = list(map(int, input().split()))
    # # 朴素做法(TLE)
    # for i in range(1, n + 1):
    #     for j in range(0, m + 1):
    #         k = 0
    #         while k <= s[i] and k * v[i] <= j:
    #             f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i])
    #         k += 1

    # print(f[n][m])

if __name__ == '__main__':
    n, m = map(int, input().split())
    f = [0 for i in range(m + 1)]
    newgood = []
    # 二进制处理,一边输入每种物品的信息,一边将si个物品i转化为数量更少的新商品
    for i in range(1, n + 1):
        v, w, s = list(map(int, input().split()))
        k = 1
        while k <= s:
            s -= k
            newgood.append([k*v, k*w])
            k *= 2
        if s > 0:
            newgood.append([s*v, s*w])


    # 01背包问题
    for t in newgood:
        j = m
        while j >= t[0]:
            f[j] = max(f[j], f[j - t[0]] + t[1])
            j -= 1
    print(f[m])





活动打卡代码 AcWing 3. 完全背包问题

shiqumi
3个月前
if __name__ == '__main__':
    N = 1010
    n, m = map(int, input().split())
    v = [0 for i in range(n + 1)]; w = [0 for i in range(n + 1)]
    # f = [[0 for i in range(m + 1)] for j in range(n + 1)]

    for i in range(1, n + 1):
        v[i], w[i] = list(map(int, input().split()))

    # 朴素做法(TLE)
    # for i in range(1, n + 1):
    #     for j in range(0, m + 1):
    #         k = 0
    #         while k * v[i] <= j:
    #             f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + k * w[i])

    #             k += 1
    # print(f[n][m])
    # 进阶做法一
    # for i in range(1, n + 1):
    #     for j in range(0, m + 1):
    #         f[i][j] = f[i - 1][j]
    #         if j >= v[i]:
    #             f[i][j]= max(f[i][j], f[i][j - v[i]] + w[i])

    # print(f[n][m])
    # 进阶做法二:一维数组
    f = [0 for i in range(m+1)]
    for i in range(1, n + 1):
        # print('----------------')
        for j in range(v[i], m + 1): 
            f[j] = max(f[j], f[j - v[i]] + w[i])
            # print(f)

    print(f[m])









shiqumi
3个月前

一、为何可以用一维数组代替二维数组?

二维数组更新方式为

f[i][j] = f[i - 1][j] # 不含i的所有选法的最大价值
if j >= v[i]: # 判断含i的选法是否成立
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
可以看出f[i][:]只依赖于f[i-1][:],所以根本没必要保留之前的f[i-2][:]等状态值;
使得空间从o(n*m)缩小到o(m),n,m分别为物品个数和背包体积

其实每个物品的体积和价值在该层循环结束后也不会再用上,这里也可以压缩为两个o(1)的空间

二、为何要逆序更新?

一维数组更新方式为

        while j >= v[i]:
            dp[j] = max(dp[j], dp[j - v[i]] + w[i])

我们只有上一层dp值的一维数组,更新dp值只能原地滚动更改;
注意到,当我们更新索引值较大的dp值时,需要用到索引值较小的上一层dp值dp[j - v[i]]
也就是说,在更新索引值较大的dp值之前,索引值较小的上一层dp值必须还在,还没被更新;
所以只能索引从大到小更新。

一维数组python代码

if __name__ == '__main__':

    n, m = map(int, input().split()) # n,m分别表示物品数量和背包容积
    v = [0 for i in range(n+1)]; w = [0 for i in range(m+1)]
    for i in range(1, n + 1):
        v[i], w[i] = list(map(int, input().split())) # 从索引1开始

    # 一维数组
    dp = [0 for i in range(m+1)]
    for i in range(1, n + 1):# i 仍代表可以选择前i个物品
        j = m
        while j >= v[i]:
            dp[j] = max(dp[j], dp[j - v[i]] + w[i])
            j -= 1
            print(dp)
        print('------------------')

    print(dp[-1])

三、用样例解释,打印dp方便理解

将每一个i循环的dp打印出来就容易理解为何要逆序遍历j(限制物品总体积)
以更新第三层为例

更新索引5

i = 3, j = 5(m=5),v[3] = 3, w[3] = 4
当前更新第3层索引5 dp[5] = max(dp[5], dp[2] + 4)
注意,等号右边的dp[5],dp[2]都必须是上一层dp的对应索引值

此时第二层为[0, 2, 4, 6, 6, 6],第三层[0, 2(未改), 4(未改), 6(未改), 6(未改), 6(正在改)]
因为本层更新dp[5]时,只能使用未更新的dp值,这些才是上一层的dp值,即索引较小的最后更新

第三层索引5更新完后为[0, 2(未改), 4(未改), 6(未改), 6(未改), 8(已经改)]

更新索引4

i = 3, j = 4(m=5),v[3] = 3, w[3] = 4此时进入j = 4
更新第三层索引4 dp[4] = max(dp[4], dp[1] + 4)
注意,等号右边的dp[4],dp[1]都必须是上一层dp的对应索引值

到这里就可以看出按索引从大到小求当前层dp值能保留上一层较小索引的dp值

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8

n = 4, m = 5

第一层dp, i = 1, v[1] = 1 , w[1] = 2, dp[j] = max(dp[j], dp[j - v[1]] + w[1])
dp[j] = max(dp[j], dp[j - 1] + 2) j从5到1
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 2, 2]
[0, 0, 0, 2, 2, 2]
[0, 0, 2, 2, 2, 2]
[0, 2, 2, 2, 2, 2]
------------------
第二层dp, i = 2, v[2] = 2 , w[2] = 4,
dp[j] = max(dp[j], dp[j - 2] + 4) j从5到2
[0, 2, 2, 2, 2, 6]
[0, 2, 2, 2, 6, 6]
[0, 2, 2, 6, 6, 6]
[0, 2, 4, 6, 6, 6]
------------------
第三层dp, i = 3, v[3] = 3 , w[3] = 4,
dp[j] = max(dp[j], dp[j - 3] + 4) j从5到3
[0, 2, 4, 6, 6, 8]
[0, 2, 4, 6, 6, 8]
[0, 2, 4, 6, 6, 8]
------------------
第四层dp, i = 4, v[4] = 4 , w[4] = 5,
dp[j] = max(dp[j], dp[j - 4] + 5) j从5到4
[0, 2, 4, 6, 6, 8]
[0, 2, 4, 6, 6, 8]
------------------
8

二维数组朴素方法(简单易懂也能AC)

if __name__ == '__main__':
    N = 1010

    n, m = map(int, input().split()) # n,m分别表示物品数量和背包容积
    v = [0 for i in range(N)]; w = [0 for i in range(N)]
    for i in range(1, n + 1):
        v[i], w[i] = list(map(int, input().split())) # 从索引1开始

    f = [[0 for i in range(N)] for j in range(N)] # 二维数组存储当前状态可达到的最大价值
    # 朴素方法
    i = 1
    while i <= n:
        j = 0
        while j <= m:
            f[i][j] = f[i - 1][j] # 不含i的所有选法的最大价值
            if j >= v[i]: # 判断含i的选法是否成立
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]) 
            j += 1
        i += 1
    for i in range(len(f)):
        print(f[i])

    print(f[n][m])


活动打卡代码 AcWing 2. 01背包问题

shiqumi
3个月前

if __name__ == '__main__':
    N = 6

    n, m = map(int, input().split()) # n,m分别表示物品数量和背包容积
    v = [0 for i in range(N)]; w = [0 for i in range(N)]
    for i in range(1, n + 1):
        v[i], w[i] = list(map(int, input().split())) # 从索引1开始

    f = [[0 for i in range(N)] for j in range(N)] # 二维数组存储当前状态可达到的最大价值
    # 朴素方法
    i = 1
    while i <= n:
        j = 0
        while j <= m:
            f[i][j] = f[i - 1][j] # 不含i的所有选法的最大价值
            if j >= v[i]: # 判断含i的选法是否成立
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]) 
            j += 1
        i += 1
    for i in range(len(f)):
        print(f[i])

    print(f[n][m])

    # 一维数组
    dp = [0 for i in range(m+1)]
    for i in range(1, n + 1):# i 仍代表可以选择前i个物品
        j = m
        while j >= v[i]:
            dp[j] = max(dp[j], dp[j - v[i]] + w[i])
            j -= 1
            print(dp)
        print('------------------')
        # 将每一个i循环的dp打印出来就容易理解为何要逆序遍历j(限制物品总体积)
        # i = 3, j = 5(m=5),v[3] = 3, w[3] = 4
        # 当前更新第3层索引5 dp[5] = max(dp[5], dp[2] + 4) # 注意,等号右边的dp[5],dp[2]都必须是上一层dp的对应索引值
        # 此时第二层为[0, 2, 4, 6, 6, 6],第三层[0, 2(未改), 4(未改), 6(未改), 6(未改), 6(正在改)]
        # 因为本层更新dp[5]时,只能使用未更新的dp值,这些才是上一层的dp值,即索引较小的最后更新

        # 此时第三层索引5更新完后为[0, 2(未改), 4(未改), 6(未改), 6(未改), 8(已经改)]
        # i = 3, j = 4(m=5),v[3] = 3, w[3] = 4 此时进入j = 4
        # 更新第三层索引4 dp[4] = max(dp[4], dp[1] + 4) # 注意,等号右边的dp[4],dp[1]都必须是上一层dp的对应索引值
        # 到这里就可以看出按索引从大到小求当前层dp值能保留上一层较小索引的dp值
    print(dp[-1])

# [0, 0, 0, 0, 0, 2]
# [0, 0, 0, 0, 2, 2]
# [0, 0, 0, 2, 2, 2]
# [0, 0, 2, 2, 2, 2]
# [0, 2, 2, 2, 2, 2]
# ------------------
# [0, 2, 2, 2, 2, 6]
# [0, 2, 2, 2, 6, 6]
# [0, 2, 2, 6, 6, 6]
# [0, 2, 4, 6, 6, 6]
# ------------------
# [0, 2, 4, 6, 6, 8]
# [0, 2, 4, 6, 6, 8]
# [0, 2, 4, 6, 6, 8]
# ------------------
# [0, 2, 4, 6, 6, 8]
# [0, 2, 4, 6, 6, 8]
# ------------------
# 8



shiqumi
3个月前

参考rebornczs大佬

class SummaryRanges:

    def __init__(self):
        # 创建存储所有间隔的列表,例如截止7存储为[1, 3, 6, 7],两个两个为一个区间左右端点
        self.d = []

    def addNum(self, val: int) -> None:
        # 二分法查找val应插入的位置,直接采用bisect库函数,其目的在于查找该数值将会插入的位置并返回,而不会插入。
        m = bisect.bisect(self.d, val)

        # 仅当m为偶数时才需要更新,因为间隔每两位为一组,若待插入位置为奇数,则一定位于某一组间隔内
        # 比如[1,3,6,7] 插入2,返回m = 1,则代表2已经在区间之中([1,3]),此时不用更新
        if m % 2 == 0:

            #处理右边界
            # 若新加入的数与其插入位置右侧的间隔有重叠部分(即差为1),则更新,使插入位置的值val
            # 比如[1,3,6,7] 插入5返回m = 2,且5 = 6 -1,说明5可以作为新连续区间的左端点,直接把原连续区间左端点覆盖为val(此处为5)即可
            if m < len(self.d) and self.d[m] - val == 1:
                self.d[m] = val


            # 若新加入的数的插入位置等于数组长度,即放置在最后,则依次添加间隔对(暂不处理左边界)
            # 比如[1,3,6,7] 插入8返回m = 4,则先无脑加入区间对8,8到数组最后,得到[1,3,6,7,8,8] 
            else:
                self.d.insert(m, val)
                self.d.insert(m, val)

            # 处理左边界
            # 若与左侧间隔有重叠部分,差为1时,删除本身左节点及前向间隔右节点
            # 比如 [1,3,6,7,8,8] ,m仍为4,此时8-7<=1,则pop(m=4)删除第一个8,再pop(m-1)删除7,得到[1,3,6,8]
            # 若[1,3,6,7] 插入7,也是m = 4,经过上一步得到[1,3,6,7,7,7],然后7-7<=1,先删第二个7,再删第一个7,得到[1,3,6,7]
            if m > 0 and self.d[m] - self.d[m - 1] <= 1:#根据现有情况选择是否和左区间合并
                self.d.pop(m)
                self.d.pop(m - 1)

    def getIntervals(self) -> List[List[int]]:
        # 列表元素两个两个输出为一个区间
        res = []
        i = 0
        while i < len(self.d):
            res.append(self.d[i:i+2])
            i += 2 
        return res
        # 间隔列表例如[1, 3, 6, 7], 按奇偶位组合填充列表返回
#         return [*zip(self.d[:: 2], self.d[1:: 2])]      #按奇偶顺序打包输出





shiqumi
3个月前
from heapq import *
class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.maxh = []; self.minh = []

    def addNum(self, num: int) -> None:
        heappush(self.minh, num) # 先无脑把新元素插到最小堆
        if len(self.maxh) and -self.maxh[0] > self.minh[0]:
            # 若最大堆非空且最大堆堆顶大于最小堆堆顶,把两者互换
            maxv = - heappop(self.maxh)
            minv = heappop(self.minh)
            heappush(self.minh, maxv)
            heappush(self.maxh, - minv)
        # 若最小堆元素个数比最大堆多2,则弹出最小堆堆顶到最大堆中
        if len(self.minh) > len(self.maxh) + 1:

            heappush(self.maxh, -heappop(self.minh))

    def findMedian(self) -> float:
        if len(self.maxh) + len(self.minh) & 1: # 总数为奇数,返回最小堆堆顶
            return self.minh[0]
        else:
            return (self.minh[0] - self.maxh[0]) / 2.0
            # 返回两个堆顶求平均,注意最大堆堆顶弹出后取相反数



# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

# 动态维护有序序列-> 手写平衡树
# 使用对顶堆,小根堆维护数据较大的一半,大根堆维护数据较小的一半
# 先无脑塞进小根堆,若两堆数据量之差大于1,则弹出小根堆堆顶到大根堆
# 总数为偶数,取两个堆顶的均值;总数为奇数,取小根堆堆顶作为中位数



shiqumi
3个月前
from heapq import *
from collections import defaultdict
class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        hash = defaultdict(lambda: 0) # 统计单词次数,默认值为0
        heap = [] # 堆
        for word in words:
            hash[word] += 1
        # for word, cnt in hash.items():
        #     # 对字典键值进行互换,因为要用次数进行堆排序
        #     t = [cnt, word]
        #     # 先无脑向堆中插入新元素,若超过k个就删去最小值
        #     heappush(heap, t)
        #     if len(heap) > k:
        #         heappop(heap)
        # res = [None for i in range(k)]
        # i = k - 1
        # while i >= 0:
        #     res[i] = heappop(heap)
        #     i -= 1
        # 当两个字符串出现次数相等,按照字母顺序排?好像不是
        # 因为堆排序内部的字符串不是按照字母顺序排,所以可能会漏掉一些没进入答案集,所以还是失败
        res = []
        for i,v in hash.items():
            res.append([v,i])
        res.sort(key=lambda x:(-x[0], x[1]))  
        #第一个要颠倒,不然从小到大,第二个本就从小到大(a,aa)
        res = res[:k]
        return [i[1] for i in res]



shiqumi
3个月前
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        self.p = []
        for i in range(n + 1): self.p.append(i) # 有多余边,所以加一

        for e in edges: # 遍历每条边
            a = e[0]; b = e[1]
            if self.find(a) == self.find(b): return [a, b] # 若该边连的两个点之前已经在同一个集合
            # 说明此边是冗余的,返回此边,代表可以删除
            self.p[self.find(a)] = self.find(b) # 否则,将两点归到同一个集合,
        return None
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

# 把所有已经连通的点放到一个集合中去





活动打卡代码 LeetCode 547. Friend Circles

shiqumi
3个月前
class UnionFind():
    def __init__(self, p):
        self.p = p

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        fa, fb = self.find(a), self.find(b)
        self.p[fb] = fa # 将b的父节点指向a的父节点

class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:                               
        n = len(M)
        data = UnionFind([i for i in range(n)])
        for i in range(n):                          
            for j in range(i):
                if M[i][j]:
                    data.union(i,j) # 合并两个朋友的朋友圈

        res = 0
        for i in range(n):
            if data.find(i) == i: # 计算有多少个根节点就有多少个朋友圈
                res += 1 

        return res