Một bài toán tương tự Knapsack

#1

Cho 1 dãy các viên đá có khối lượng là A_1, A_2,..., A_k
Chọn bất kì 2 viên đá đập chúng với nhau:
ví dụ chọn 2 viên A_m và A_n

  • Nếu A_m = A_n thì chúng sẽ biến mất
  • Nếu A_m > A_n thì A_n := 0 và A_m := A_m - A_n
    Return khối lượng nhỏ nhất có thể của viên đá còn lại cuối cùng. Nếu không còn viên đá nào Return 0.

Trong Solution của bài này có nói là: khối lượng nhỏ nhất có thể của viên đá cuối cùng bằng với độ chênh lệch nhỏ nhất của 2 phần (chia các viên đá đó thành 2 phần)
Cho e hỏi làm sao chứng minh nó đúng ?

#2

Thì ta cứ chia thành 2 phần X với Y, rồi lấy viên bên X đập với 1 viên bên Y. Còn dư thì lấy tiếp 1 viên bên đống kia đập tiếp. Cuối cùng còn dư sẽ là chênh lệch 2 phần. Bài toán kêu tìm nhỏ nhất => chia sao cho 2 bên lệch nhau ít nhất thôi.

3 Likes
#3

Ý mình là làm sao chắc chắn 2 viên chọn ra phải là 1 viên bên X, 1 viên bên Y? Vì sao nếu chọn 2 viên cùng bên thì không cho kết quả tối ưu?

#4

Ở kia mình chưa nói gì tới kết quả tối ưu cả, mà chỉ nêu ra 1 cách để chọn, và vô tình chúng ta có thể tối ưu được nếu làm theo cách chọn như vậy thôi.

2 Likes
#5

Thật khó để từ đầu có thể nghĩ ra được nó bằng độ chênh lệch nhỏ nhất của 2 phần :frowning:

#6

Uầy, chỉ là bài toán ad-hoc thôi mà.
Bây giờ như vầy.
Không cần chia 2 phần gì hết.
Bạn chọn bất kỳ 2 viên đá trong tập A.
Rồi đập chúng với nhau.
(tới đây vẫn là làm đúng theo lời đề bài)
Rồi sẽ ghi nhận khối lượng viên bị hủy vào 1 cột.
Rồi lấy tiếp 1 viên khác từ A đập vào viên còn lại kia. Có 2 trường hợp:

  • Viên còn lại ban đầu bị hủy => Ghi nhận khối lượng viên đó vào cột thứ 2
  • Nếu là viên mới lại bị hủy => Ghi nhận khối lượng vào cột 1
    Cứ lần lượt như vậy thì cuối cùng còn lại một mẫu => cho nó vào cái cột “khác” cột bỏ viên kế cuối
    Vậy là giờ có 2 cột, với khối lượng còn lại chính là chênh lệch tổng khối lượng trong 2 cột này.

Rồi, bây giờ làm sao để được nhỏ nhất => chênh lệch 2 cột nhỏ nhất => quay lại bài toán chia 2 phần sao cho chênh lệch nhỏ nhất

6 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?