Bài toán ba lô 1

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

jumptozero

Dạng bài

Điểm: 350 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Có \(N\) viên bi, được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), viên bi thứ \(i\) có khối lượng là \(w_i\) và có giá trị là \(v_i\).

\(Kaninho\) quyết định chọn một số viên bi từ \(N\) viên bi trên và bỏ vào ba lô để đi chơi. Sức chứa của ba lô là \(W\), có nghĩa là tổng khối lượng của các viên bi được chọn phải không được quá \(W\).

Tìm tổng giá trị lớn nhất có thể của các viên bi được chọn để bỏ vào ba lô.

Input

Dòng thứ nhất chứa hai số nguyên \(N,W(1\le N\le 100,1\le W\le 10^5)\)
\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i,v_i(1\le w_i\le W,1\le v_i\le 10^9)\)

Output

In ra giá trị cần tìm.

Example

Test 1

Input

Output

Note

Giải thích: Viên bi thứ \(1\) và \(3\) sẽ được chọn để bỏ vào ba lô. Vì chúng có tổng khối lượng không quá \(8\) và có giá trị lớn nhất là \(90\).

Bình luận

-2

Vodangngoclam 6:02 p.m. 22 Tháng 6, 2024 ← chỉnh sửa 3 →

Ko chép nha

https://ideone.com/kAEZ4s

2 phản hồi

-2

I HATE KNAPSACK 🙁 python

def printRes(res):
    for i in res:
        print(i)
n,w=map(int,input().split())
a,b=[0],[0]
for i in range(n):
    c,d=map(int,input().split())
    b.append(c)
    a.append(d)
#print(a,b)
res=[[0]*(w+1) for i in range(n+1)]
#printRes(res)
for i in range(1,n+1):
    for j in range(1,w+1):
        res[i][j]=res[i-1][j]
        if j>=b[i]:
            res[i][j]=max(res[i-1][j],res[i-1][j-b[i]]+a[i])
#printRes(res)
print(res[n][w])

1 phản hồi