THUHOACH - Thu hoạch vụ mùa

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
Hieu Nguyen
Problem type
Allowed languages
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Hiện đang vào mùa thu hoạch ngô, nhà Tí có một chiếc công nông tải trọng có hạn, chỉ chở được tối đa ~C~ (kg), trong khi đó nhà Tí lại thu được ~N~ bao ngô, bao thứ ~i~ có khối lượng là ~w_i~ (kg), hãy giúp Tí tính xem một chuyến xe nhà Tí có thể chở được khối lượng ngô tối đa là bao nhiêu?

Input

  • Dòng đầu chứa hai số nguyên dương ~N,C~;
  • Dòng thứ hai chứa ~N~ số nguyên dương ~w_1, w_2, …, w_N~, mỗi số cách nhau bởi một dấu cách.

Giới hạn:

  • ~1 ≤ N ≤ 20, 1 ≤ C, w_i ≤ 50000~.

Output

  • Một số nguyên duy nhất là khối lượng ngô tối đa xe nhà tí chở được trong một chuyến.

Sample

Input #1
5 259
81 58 42 33 61
Output #1
242

Hint

Giải thích #1:

  • Chở các bao ngô số ~1, 2, 3, 5~ ta có tổng khối lượng là: ~81+58+42+61 = 242~, đây là tổng khối lượng ngô lớn nhất có thể chở được.

Problem source: Chuyên Sơn La Online Judge

Comments

Please read the guidelines before commenting.


  • 0
    ngtuananh  commented on Dec. 11, 2024, 5:45 a.m.

    def main(): SODOVATTOIDA = 105 TRONGLUONGLON_NHAT = 10005

    phuong_an = [0] * TRONG_LUONG_LON_NHAT

so_do_vat, gioi_han = map(int, input().split())

for _ in range(so_do_vat):
    x = int(input())
    if x <= gioi_han:  # Chỉ xử lý các đồ vật phù hợp
        for j in range(gioi_han, x - 1, -1):
            phuong_an[j] = max(phuong_an[j], phuong_an[j - x] + x)

print(phuong_an[gioi_han])

    if name == "main": main()


  • 1
    Minh_Khoa  commented on Oct. 11, 2024, 3:47 a.m.

    mấy bn python cho mình xin code với


  • 0
    kieuly123  commented on April 20, 2024, 8:21 a.m.

    test 5 6 là gì v ạ


  • 0
    bnshuyenthoainvta  commented on March 23, 2024, 3:58 a.m.

    Ý tưởng là dùng quay lui tìm tất cả tổng max của số bao ngô có thể chọn từ 0 đến n; sau đó lấy một mảng khác hứng kết quả các tổng max đó; sau đó so sánh kết quả trong tổng max đó với trọng tải của xe để ra được số kg ngô lớn nhất có thể chở.


  • 0
    NguyenBuiVN  commented on March 3, 2024, 11:55 a.m.

    ủa bài quy hoạch động mà mình cài quay lui cũng ac này =))


    • 0
      lehongduc  commented on May 15, 2024, 2:28 p.m.

      do N<=20 ak chứ mà N<=10^6 là xong đáy:)


  • 1
    TQThong2k11  commented on Dec. 7, 2023, 4:13 a.m.

    ai cho mình xin í tưởng đc ko bí quá :v


    • 0
      quanvannam252  commented on Feb. 22, 2024, 9:50 a.m.

      dùng quy hoạch động nha


  • 1
    leminhtripython  commented on Nov. 3, 2023, 2:36 p.m.

    test case 5 là gì vậy ạ


  • -5
    huhu_tuingucode  commented on Sept. 14, 2023, 10:34 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.