Bài toán. Trong siêu thị có n gói hàng đánh số từ 1 đến n (n≤1000), gói hàng thứ i có trọng lượng Wi ≤1000 và giá trị Vi ≤1000. Một tên trộm đột nhập vào siêu thị mang theo một cái túi có thể mang được tối đa trọng lượng M ≤1000. Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất?
Dữ liệu vào: Cho từ file văn bản BAG.INP
Dòng đầu chứa hai số nguyên dương n, M
n dòng tiếp theo, dòng thứ i ghi hai số nguyên dương Wi và Vi .
Kết quả: Ghi ra file văn bản BAG.OUT
Dòng đầu ghi giá trị lớn nhất tên trộm có thể lấy được.
Dòng thứ hai ghi chỉ số của những gói hàng bị lấy theo thứ tự chỉ số từ nhỏ đến lớn.
Ví dụ:
BAG.INP
BAG.OUT
5 11
3 3
4 4
5 4
9 10
4 4
11
1 2 5
Const fin ='BAG.INP'; fout='BAG.OUT'; Var W,V:array[1..1000] of Integer; T:array[0..1000,0..1000] of Longint; n,m,i,j,max:Longint; f:Text; Begin Assign(f,fin); Reset(f); Readln(f,n,m); For i:=1 to n do Readln(f,W[i],V[i]); Close(f); For i:=1 to n do For j:=1 to M do Begin max:=T[i-1,j]; If j>=W[i] then If max<T[i-1,j-W[i]] + V[i] then max:=T[i-1,j-W[i]] +V[i]; T[i,j]:=max; End; Assign(f,fout); Rewrite(f); Writeln(f,T[n,M]); j:=M; For i:=n downto 1 do If T[i,j]<>T[i-1,j] then Begin V[i]:=0; j:=j-W[i]; End; For i:=1 to n do If V[i]=0 then Write(f,i,' '); Close(f); End.
Đỗ Thành
Dãy con đơn điệu tăng dài nhất trong Pascal Slide luận văn thạc sĩ kế toán Dịch vụ thiết kế slideBài viết mới
Các mẹo Finder giúp tìm file nhanh gấp nhiều lần trên MacBook
Chụp ảnh, quay màn hình trên MacBook: Công cụ mặc định mạnh mẽ
Quản lý cửa sổ và Desktop ảo trên macOS hiệu quả
Những cài đặt macOS nên tắt để MacBook chạy mượt hơn, ổn định hơn
20 phím tắt MacBook giúp tăng gấp đôi năng suất làm việc
Hướng dẫn cài đặt và gỡ ứng dụng trên macOS đúng cách, an toàn
MacBook Air hay MacBook Pro? Phân tích theo nhu cầu thực tế
Trackpad trên MacBook: Hướng dẫn giúp thao tác nhanh gấp đôi
Các lỗi thường gặp trên MacBook và cách khắc phục đơn giản
Chuyển từ Windows sang MacBook: Làm quen nhanh trong 7 ngày hiệu quả
Phím tắt Safari trên MacBook: Bí quyết duyệt web nhanh gấp đôi
MacBook dành cho người mới: Những điều cần biết trong 24 giờ đầu
Những mẹo sử dụng thông minh với Macbook
Phương pháp dạy học đảo ngược (Flipped Learning / Flipped Classroom)
Liệt kê tất cả các phương pháp dạy học truyền thống đến hiện đại
AI Generated Content – “Cỗ máy sáng tạo” thay đổi ngành nội dung
Multimodal AI: Đưa AI tiệm cận năng lực tư duy của con người
Tương lai AI tự lập: Khi trí tuệ nhân tạo bước ra khỏi hộp chat
Phòng học đa năng STEM: Nền tảng đổi mới giáo dục thời 4.0
Dạy học STEM – Con đường đổi mới giáo dục trong kỷ nguyên 4.0
Magic School – Trợ lý AI toàn diện cho giáo viên thời 4.0
Napkin AI – Khi Ý Tưởng Biến Thành Hình Ảnh Trong Chớp Mắt
Diffit – Trợ thủ AI Đột Phá Giúp Giáo Viên Cá Nhân Hóa Bài Giảng
LaTeX – “Ngôn ngữ” soạn thảo của giới khoa học và kỹ thuật
