Tìm số tiền cần trả ít nhất
mình thấy đề đã qúa rõ ràng, không có đánh đố hay giải thuật gì ở đây cả
với mỗi mặt hàng thì chọn siêu thì nào rẻ hơn hoặc siêu thị A nếu giá ngang nào, tính tổ số tiền là xong
vậy thì vòng for là xong
bạn đang gặp vấn đề gì?
1 Like
Có thêm ràng buộc là tổng số món hàng từ siêu thị A.
3 Likes
chỗ tổng số tiền ít nhất
bạn hiểu ví dụ chưa? bạn có thể giải thích được kết quả ví dụ không
a[1]>b[1] nên lấy b nhưng chỗ a[3]<b[3]thì lấy a mà chỉ lấy 2 còn lấy b 2 do lấy 4 cái thì tiền nhiều hơn
Giải thích như vầy thì không biết cách làm là đúng rồi.
B1: Cứ mua như bình thường, bên nào giá tiền ít hơn thì mua:
0 0 4 8
5 2 0 0
B2: Nếu tổng số hàng hóa bên A mà mua quá số lượng: giảm từng mặt hàng bên A, mua bên B sao cho chênh lệch giá 2 bên ít nhất:
- Tống số mặt hàng mua bên A là 4+8 = 12 => vượt
- Cần giảm 4 về 3 hoặc 8 về 7 => Giảm 4 về 3 do chênh lệch là 7-5=2, so với 14-6=8 nếu giảm 8 về 7
=> Số hàng mới:
0 0 3 8
5 2 1 0
B3: Lặp lại bước 2 nếu tổng A vẫn dư
PS:
Dĩ nhiên cái vụ lặp này có thể tối ưu, nhưng mà chưa code ra code đúng thì đừng có nghĩ tới tối ưu làm gì
PPS:
B2: Nếu tổng số hàng bên A vượt quá số lượng: Tìm mặt hàng mua bên A sao cho chênh lệch giá với bên B là ít nhất rồi trừ đi min(số lượng dư, số lượng mua bên A)
B3: Lặp lại B2 đến khi hết vượt số lượng
2 Likes
phải quy hoạch động như knapsack gì đó thôi 
“túi” có “thể tích” = r, C[i] món hàng thứ i có “thể tích” là 1 và trị giá = B[i] - A[i].
như ví dụ thì có:
- 5 món hàng giá trị 2-5 = -3
- 2 món hàng giá trị 5-12 = -7
- 4 món hàng giá trị 7-5 = 2
- 8 món hàng giá trị 14-6 = 8
giải bài toán knapsack cho 5+2+4+8 = 19 món hàng là được
nhưng do ở đây tất cả các món hàng đều có thể tích là 1 nên toy nghĩ tham lam có thể đúng 
cứ lấy món hàng theo thứ tự giá trị to nhất tới nhỏ nhất, nhưng đừng lấy món hàng có giá trị âm.
3 Likes
bài này 1 vòng for thôi chứ đâu có giải thuật gì, đề bài nói rất rõ, mua làm sao để chỉ trả số tiền ít nhất
với mỗi món hàng thì chọn bên rẻ mà mua, nếu bên rẻ là A thì bị giới hạn số lượng, thì cứ việc mua đến giới hạn của A rồi phần còn lại mua bên B thôi
thì cứ làm như bạn đã mô tả thôi,
1 Like
Chuẩn. Do chỉ quan tâm tới số tiền cần trả thì chỉ cần tham lam là được. Nhưng nếu có thêm điều kiện về thể tích thì sẽ phức tạp hơn
Không chắc là /me hiểu đúng chưa, nhưng chả phải làm như vầy thì sẽ ra như bên dưới sao?
0 0 4 6
5 2 0 2
Bởi vì tới chỗ món thứ ba, do A rẻ hơn mà vẫn chưa quá giới hạn, nên vẫn lấy luôn 4 món bên A, sau đó tới món cuối mới chọn 6 món bên A, 2 món bên B để bên A đủ 10 món thôi?
2 Likes
sorry mọi người, do mình load cái đề bài không hết cái ví dụ nên xảy ra hiểu lầm về số lượng 10 của cửa hàng A (là tổng hàng có thể cung cấp thay vì số lượng mỗi loại hàng)
về bài này, mình xin có ý kiến như sau
- Để chi phí là thấp nhất, hiển nhiên sẽ luôn chọn bên bán giá rẻ
- Tuy nhiên, nhà cung cấp A thì có giới hạn số hàng có thể mua (như ví dụ là 10), nên những suất mua hàng ở A nên ưu tiên những deal có độ lệch lớn
- Như vậy, cần tạo ra 1 mảng tạm gọi là D, với Di là chênh lệch giá giữa Ai và Bi, như ví dụ trên, ta sẽ được 3 7 -2 -8 (ý nghĩa là mua món hàng thứ i ở cửa hàng A sẽ lệch bao nhiêu tiền so với B)
- Từ đó, bắt đầu chọn những mặt hàng có độ tiết kiệm lớn nhất để mua ở A, đầu tiên là món hàng có i = 3, nếu mua ở A, sẽ tiết kiệm được 8 đơn vị tiền, tiết kiệm được nhiều nhất, nên mua nhiều nhất có thể
Cụ thể là số lượng cần là 8, vậy thì mua 8 món hàng số 3 (index) ở A, lúc này còn 2 suất mua ở A
Tương tự, nếu suất mua ở A vẫn còn thì mua tiếp, ví dụ sau khi chọn món số 3 (index) thì còn 2 suất
lại chọn món hàng tiết kiệm được nhiều nhất, là món có index 2, đang cần 4, vậy mua 2 suất ở A, và 2 suất ở B.
Nếu hết suất mua ở A thì sau đó toàn bộ mua ở B
-> bài này n = 1000 nên lười có thể dùng 2 for (chạy n^2), đỡ phải sort
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?