BÀI TẬP BÀI 2: GIẢI THUẬT THAM LAM

Bài 71. Một nông dân đang muốn trồng hoa vào khu vườn của mình. Để cho khu vườn trở nên thật màu sắc ông quyết định trồng nhiều loài hoa khác nhau vào khu vườn. Mỗi loài hoa có mội cách trồng khác nhau do đó ông sẽ trồng từng loài hoa vào các ngày liên tiếp nhau. Cháu của ông rất mong chờ được thấy tất cả loài hoa trong khu vườn đều nở hoa trông sẽ tuyệt vời như thế nào. Tuy nhiên mỗi loài hoa lại có thời gian phát triển từ lúc trồng tới lúc nở hoa khác nhau.

Lựa chọn tham lam là trồng cây có thời gian phát triển lâu nhất trước.

Code python

def date_all_flowers_bloom(a):# a is a list of the development time of the flowers
  a.sort(reverse=True)
  k,result,n=1,0,len(a)
  while k<=n:
    if a[k-1]+k>result:
      result=a[k-1]+k
    k+=1
  return result

Bài 72. Anh Lộc làm nghề phụ hồ cho một công ty xây dựng, Anh nhận thấy rằng mỗi loại gạch đều có độ cứng khác nhau. Giả sử rằng viên gạch có độ cứng k chỉ có thể chịu được tối đa k viên gạch khác chồng lên nó, nếu nhiều hơn thì nó sẽ bị vỡ. Anh Lộc muốn lấy gạch và xếp chúng chồng lên nhau thành một chồng gạch cao nhất có thể mà không để vỡ viên gạch nào. Hãy tìm và in ra màn hình xem anh Lộc có thể xếp chồng gạch có độ cao lớn nhất là bao nhiêu.

Lựa chọn tham lam là xếp viên gạch có độ cứng lớn nhất trước.

Code python

def stack_bricks(a):
    a.sort(reverse=True)
    stiffness,k,n=a[0],1,len(a)
    for i in range(1,n):
        stiffness,k=stiffness-1,k+1
        if stiffness>a[i]:
            stiffness=a[i]
        if stiffness==0:
            return k
    return n

Phần bài tập này mình làm trong khóa học của funix dịch từ phần bài tập trong khóa học Data structures and algorithms của coursera. Chú ý phần bài tập này của coursera trả phí mua khóa học thì mới có. Hoặc bạn có thể mua khóa học của funix có dịch sẵn rất tiện lợi và có mentor giúp đỡ.

Link chi tiết bài tập của cousera https://drive.google.com/file/d/1sVmxysl6m9TSlr-ZWX-ifRwVyaPM8M-S/view?usp=sharing

Lab 2.1. Đổi tiền bằng thuật toán tham lam.

Tìm số lượng đồng xu tối thiểu cần thiết để đổi giá trị input (một số nguyên) thành tiền xu với mệnh giá 1, 5 và 10

Lựa chọn tham lam là đổi tờ tiền cần đổi sang các tờ tiền có mệnh giá lớn nhất có thể và nhỏ hơn hoặc bằng tờ tiền cần đổi.

Code python:

def MONEY_CHANGE(m):
    M,R=[10,5,1],[]
    for i in M:
        while m>=i:
            R.append(i)
            m=m-i
        if m==0:
            return (R,len(R))

Ngoài ra ta có thể tối ưu code trên bằng một số phân tích số học như sau.

$m=10.q_1+r_1,r_1=5.q_2+r_2,m=10.q_1+5.q_2+r_2=5(2.q_1+q_2)+r_2$ 

Suy ra số lượng xu đổi ít nhất là $m//10+r_1//5+r_2=m//10+(m\%10)//5+m\%5$

Lab 2.3. Tối đa doanh thu từ vị trí đặt quảng cáo trực tuyến

Bạn có n quảng cáo cần bố trí trên một trang mạng nổi tiếng. Với từng quảng cáo, bạn biết người quảng cáo sẽ sẵn sàng chi trả bao nhiêu tiền cho một cú nhấp chuột vào quảng cáo. Bạn đã thiết lập n vị trí trên trang mạng và ước tính số lượng cú nhấp chuột mỗi ngày vào từng quảng cáo ở mỗi vị trí. Mục tiêu của bạn là phân bổ các quảng cáo ở các vị trí khác nhau để tối đa doanh thu.

Lựa chon tham lam là đưa quảng cáo có số tiền lớn nhất cho một cú nhấp chuột vào vào vị trí có số lượng cú nhấp chuột nhiều nhất.

Code python:

def Maximum_Scalar_Product(A,B):
    result=0
    while len(A)>0:
        am,bm=max(A),max(B)
        result+=am*bm
        A.remove(am)
        B.remove(bm)
    return result

Gọi cặp $(a_i,b_i), i=1,...,n$ lần lượt là giá trị lớn nhất của A và B 

$S=a_i.b_q+a_q.b_j, S'=a_i.b_i+a_q.b_q,S'-S=(a_i-a_q).(b_i-b_q) \geq 0$

Thời gian chạy của thuật toán là $O(n^2)$

Ngoài ra ta có thể quy bài toán trên về bài toán sắp xếp hai dãy.

Lab 2.4. Bạn có trách nhiệm thu thập chữ ký của tất cả những người thuê nhà trong một tòa nhà nào đó. Với mỗi người thuê nhà, bạn biết thời gian họ có mặt ở nhà. Bạn muốn thu thập toàn bộ chữ ký sao cho bạn chỉ cần đến tòa nhà ít lần nhất có thể. Mô hình toán học cho bài toán này như sau: Cho một tập hợp các đoạn trên một đường và mục tiêu của bạn là đánh dấu ít điểm nhất có thể trên một đường sao cho mỗi đoạn chứa ít nhất một điểm.

Mô tả bài toán 

Cho một tập hợp n đoạn $\left \{[𝑎_0, 𝑏_0], [𝑎_1, 𝑏_1], . . . , [𝑎_{𝑛−1}, 𝑏_{𝑛−1}]\right \}$ với các tọa độ số nguyên trên một đường, hãy tìm số điểm m tối thiểu sao cho mỗi đoạn chứa ít nhất 1 điểm. Hay, tìm tập hợp các số nguyên $X$ nhỏ nhất sao cho trên mỗi đoạn $[𝑎_𝑖, 𝑏_𝑖]$ có một điểm $x \in X$ thỏa mãn $a_i  \leq  x \leq b_i.$

Code python

import sys
from collections import namedtuple
Segment=namedtuple('segment','start end')#Segment là đoạn
def optimal_points(Segments):
    points=[]
    Segments.sort(key=lambda x: x[1])
    point=Segments[0].end
    points.append(point)
    for s in Segments:
        if s.start>point:
            point=s.end
            points.append(point) 
    return points
if __name__=='__main__':
    input=sys.stdin.read()
    n,*data=map(int,input.split())
    Segments=list(map(lambda x: Segment(x[0],x[1]),zip(data[::2],data[1::2])))
    points=optimal_points(Segments)
    print(len(points))
    for p in points:
        print(p,end=' ')

Lab 2.5. Tối đa số lượng giải thưởng trong một cuộc thi

Giới thiệu bài toán

Bạn sắp tổ chức một cuộc thi thú vị cho trẻ em. Quỹ giải thưởng bạn có là n chiếc kẹo. Bạn muốn dùng những chiếc kẹo này để trao cho 𝑘 vị trí dẫn đầu trong cuộc thi với điều kiện là vị trí cao hơn sẽ nhận được nhiều kẹo hơn. Để khiến nhiều đứa trẻ vui vẻ nhất có thể, bạn sẽ phải tìm ra giá trị k lớn nhất.

Code python

import sys
def optimal_summands(n):
    summands = []
    l=1
    while n>2*l:
        summands.append(l)
        n,l=n-l,l+1
    summands.append(n)
    return summands
if __name__=='__main__':
    input=sys.stdin.read()
    n=int(input)
    summands=optimal_summands(n)
    print(len(summands))
    for i in summands:
        print(i,end=' ')