Bình luận

• 
  

  27

  

  hieuhfgr  đã bình luận lúc 30, Tháng 9, 2025, 16:00

  Mô sai (my sol)

  Hint:

  Quy Hoạch Động cái túi và có thêm 1 trạng thái để lưu trữ.

  Đổi biến.

  Solution:

  Chưa xét về việc lấy thêm 1 đồ vật, đây đơn giản là quy hoạch động cái túi đơn giản và thêm phần đảo nhãn.

  Gọi ~dp_{i, c}~ là khối lượng bé nhất khi xét các đồ vật từ ~1~ đến ~i~ và có giá trị là ~c~.

  Bây giờ, vì đề bài còn yêu cầu thêm việc lấy thêm 1 đồ vật cho tay còn lại, ta đơn giản thêm một chiều quy hoạch động.

  Gọi ~dp_{i, c, s}~ là khối lượng bé nhất khi xét các đồ vật từ ~1~ đến ~i~ và có giá trị là ~c~ và tay còn lại có đang cầm đồ vật hay chưa (~s \in {0, 1}~).

  trạng thái ban đầu: ~dp_{0, 0, 0} = 0~.

  chuyển trạng thái:

  Trường hợp bỏ vào cái túi

  • ~dp_{i + 1, c, s} = min(dp_{i, c, s})~
  • ~dp_{i + 1, c + cost_{i+1}, s} = min(dp_{i, c, s} + weight_{i+1})~

  Tay còn lại cầm đồ vật

  • ~dp_{i + 1, c + cost_{i+1}, 1} = min(dp_{i, c, 0})~ nếu ~weight_{i+1} \leq H~

  Kết quả bài toán: ~c_{max}~ với ~min(dp_{n, c_{max}, 0}, dp_{n, c_{max}, 1}) <= W~

  Lần ~8~ viết sol mong mọi người đừng downvote T_T

• 
  

  2

  

  HeroMinhSteve  đã bình luận lúc 4, Tháng 6, 2025, 16:54

  Spoiler

  https://ideone.com/DPKIFK