Bài toán cái túi

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
kitsune
Dạng bài
Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho \(n\) món đồ được đánh chỉ số từ \(1\) đến \(n\), món đồ thứ \(i\) có trọng lượng \(w_{i}\) và giá trị \(v_{i}\). Hãy chọn một số món đồ sao cho tổng trọng lượng không vượt quá \(m\) và tổng giá trị là lớn nhất có thể.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n, m \leq 10^{5})\).
  • Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(w_{i}\) và \(v_{i}\) \((1 \leq w_{i}, v_{i} \leq 10)\).

Output

  • Một dòng duy nhất chứa một số nguyên là tổng giá trị lớn nhất tìm được.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(n, m \leq 10^{3}\).
  • Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
6 15
6 5
5 6
6 4
6 6
3 5
7 2
Output 
17

Bình luận

  • ronaldo12345 • 10:47 a.m. 28 Tháng 1, 2025 •

    bài này sử dụng dp + prefix-sum có ac nổi ko ạ 🙂

    0
    Phản hồi
    • toi_la_ai • 10:59 a.m. 28 Tháng 1, 2025 •

      Thì bạn tính ra độ phức tạp ổn thì AC thôi chứ hỏi làm gì

      Mà bài này mà kết hợp Prefix Sum thì giải quyết như thế nào nhỉ? Mình thấy lạ

      0
      Phản hồi
      • ronaldo12345 • 11:03 a.m. 28 Tháng 1, 2025 • ← đã chỉnh sửa 

        prefix[0] = dp[0];
        for (int j = 1; j <= m; ++j) {
            prefix[j] = max(prefix[j - 1], dp[j]);
        }
    }

        thế thôi bạn

        0
        Phản hồi
        • toi_la_ai • 11:06 a.m. 28 Tháng 1, 2025 •

          Cái này là Prefix Max chứ có phải Prefix Sum đâu

          Xem qua code của bạn thì mình thấy độ phức tạp tận \(O(n\times m)\) thì sao qua được. Với lại mình chả biết cái mảng prefix của bạn để làm gì luôn ý, cái công thức DP cũng chả dùng đến nó

          0
          Phản hồi