Bài toán cái túi 0/1

Khó

quy hoạch động5 test · 3 giây

Có n đồ vật, vật i nặng wᵢ và có giá trị vᵢ. Túi chịu được tối đa W. Mỗi vật lấy tối đa một lần. Tổng giá trị lớn nhất có thể mang là bao nhiêu?

dp[c] = giá trị lớn nhất với sức chứa c. Duyệt c từ lớn về nhỏ để mỗi vật chỉ được dùng một lần.

Dữ liệu vào

Dòng 1: n W (1 ≤ n ≤ 100, 0 ≤ W ≤ 10⁵).

n dòng: w v (1 ≤ w ≤ 10⁵, 1 ≤ v ≤ 10⁹).

Tổng giá trị lớn nhất (có thể vượt 32-bit).

Input

Output

Lấy vật 1 và 3: nặng 8, giá trị 90

Input

1 2
3 100

Output

Không vật nào vừa túi

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.