BÀI 4: TÚI BA GANG (*NNLT: Python) Trong truyện cổ tích "Cây Khế" ta đã biết rằng chim thần chở người anh với một cái túi ba gang đến hòn đảo đầy vàng bạc châu
BÀI 4: TÚI BA GANG
(*NNLT: Python)
Trong truyện cổ tích "Cây Khế" ta đã biết rằng chim thần chở người anh với một cái túi ba gang đến hòn đảo đầy vàng bạc châu báu. Người em băn khoăn không biết chọn đồ vật nào cho vào túi vì chỉ có một cái túi ba gang. Giả sử rằng trên hòn đảo kia có N đồ vật khác nhau, đồ vật thứ i có giá trị là ai và có thể tích là bi. Cũng giả sử rằng cái túi mà người em mang đi chỉ có thể tích là M. Bạn hãy giúp người em chọn ra trong N đồ vật trên một số đồ vật sao cho tổng thể tích của các đồ vật được chọn không vượt quá M và tổng giá trị các đồ vật được chọn là lớn nhất.
Input: Cho trong file văn bản CAYKHE.INP
• Dòng đầu tiên ghi hai số N, M (N,M≤100)
• N dòng tiếp theo, dòng thứ i ghi hai số ai và bi lần lượt là giá trị và thể tích của đồ vật thứ i (ai, bi≤100)
Output: Ghi ra file văn bản CAYKHE.OUT
• Dòng đầu tiên ghi tổng giá trị lớn nhất có thể cho vào trong túi
• Dòng thứ hai ghi số hiệu các đồ vật được cho vào trong túi. Đầu tiên ghi K là số lượng đồ vật được chọn, tiếp theo là K số thể hiện số hiệu các đồ vật được chọn.
VD:
CAYKHE.INP CAYKHE.OUT
5 10 63
20 3 3 1 2 4
19 1
30 7
24 3
15 6
Skill problem nên cần giúp ạ:) (Không pm thứ 3)
Lời giải 1 :
n,m=map(int,input().split())
x=[[0,0,0]]
y=[]
#meothinhle
for i in range(1,n+1):
c,p=map(int,input().split())
x.append([c,p])
f=[[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
for j in range(1,m+1):
f[i][j]=f[i-1][j]
if j>=x[i][1]:
f[i][j]=max(f[i-1][j],f[i-1][j-x[i][1]]+x[i][0])
print(f[n][m])
for i in range(n,0,-1):
if f[i][m]!=f[i-1][m]:
y.append(i)
m-=x[i][1]
print(len(y),*y[::-1])
bài này làm bằng python dùng quy hoạch động chạy nhanh nhưng bị tràn bộ nhớ nha
Lời giải 2 :
n,m=map(int,input().split())
x=[[0,0]]+[list(map(int,input().split())) for_in range(n)]
f=[[0]*(m+1) for_in range(n+1)]
for i in range(1,n+1):
for j in range(m+1):
f[i][j]=f[i-1][j]
if j>=x[i][1]:
f[i][j]=max(f[i][j],f[i-1][j-x[i][1]]+x[i][0])
print(f[n][m])
y=[]
for i in range(n,0,-1):
if f[i][m]!=f[i-1][m]:
y.append(i)
m-=x[i][1]
print(len(y),*y[::-1])Bạn có biết?
Tin học là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng. Tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin. Hãy tận dụng sức mạnh của tin học để giải quyết các vấn đề và sáng tạo ra những giải pháp mới!
Nguồn :
Wikipedia - Bách khoa toàn thưTâm sự lớp 10
Lớp 10 - Năm đầu tiên ở cấp trung học phổ thông, chúng ta sẽ có nhiều bạn bè mới đến từ những nơi khác nhau. Ngôi trường mới, xa nhà hơn, mở ra một thế giới mới với nhiều điều thú vị. Hãy mở lòng đón nhận và tận hưởng những trải nghiệm mới!
Nguồn :
sưu tậpCopyright © 2021 HOCTAPSGK