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
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
NotebookLM – Học và nghiên cứu với AI “hiểu rõ nguồn”
So Sánh Ưu – Nhược Điểm Các Công Cụ AI Hàng Đầu Thế Giới (2025)
“Mất dấu” màn hình Home trong office: Cách khắc phục đơn giản
Nhiều gã khổng lồ e dè trước sắc lệnh AI mới của Tổng thống Trump
ChatGPT vượt mốc 2,5 tỷ truy vấn mỗi ngày
Laptop đáng mua nhất 2025: Toàn cảnh “mùa vàng” cho mọi nhu cầu
Máy tính đồ họa 2025: Cuộc chơi của những “quái thú” hiệu năng
Cuộc chiến âm thầm giữa nghệ sĩ lồng tiếng và trí tuệ nhân tạo
Tại sao tôi cảm thấy cô đơn dù xung quanh có nhiều người?
Nên sống thật với chính mình hay cố gắng làm hài lòng người khác?
Ước mơ thực sự của tôi là gì? Hành trình khám phá bản thân
“Tôi là ai? Tôi sống vì điều gì?” – Hành trình tìm về chính mình
