Ngân có một bài giải thuật bị bế tắc, mong các bạn giúp đỡ cho Ngân.
Tại một buôn làng nọ, có một ngời cha và hai người con trai. Người cha mất đi để lại cho hai con trai một số gia tài (nhà cửa, trâu bò, cồng chiêng….). Hai người con không biết phân chia như thế nào cho đều nhau nên mới nhờ đến già làng chia gia tài giúp. Già làng cũng chịu thua và nhờ anh (chị) thiết kế giúp một giải thuật để chia gia tài cho hai anh em.
Giả sử rằng người cha có n món gia tài, giá trị của chúng lần lượt là v1, v2,…vn (tất cả đều là số nguyên dương). Hãy giúp già làng chia gia tài cho hai người con sao cho tổng giá trị gia tài của hai anh em chênh lệch nhau ít nhất. Có nghĩa là nesu gọi A là tổng giá trị gia tài của anh, B là tổng giá trị gia tài của người em, thì | A – B | nhỏ nhất. Có thể nhận thấy rằng để độ chênh lệch nhỏ nhất thì tổng giá trị gia tài của từng người gần với 1/2 tổng số gia tài nhất.
Ví dụ: Người cha có 5 món gia tài có giá trị lần lượt là: 3, 4, 2, 7, 5. Ta có thể chia như sau:
- Người anh (3 món): 3 + 2 + 5 = 10
- Người em (2 món): 4 + 7 = 11
- Độ chênh lệch: | 10 – 11 | = 1
Câu 1: Áp dụng kỹ thuật háu ăn (greedy) để thiết kế giải thuật chia gia tài. Tính độ phức tạp thời gian của giải thuật theo n.
Câu 2: Áp dụng kỹ thuật chia để trị thiết kế giải thuật (đệ quy) tính độ chênh lêch giá trị gia tài của hai anh em sao cho độ chênh lệch này nhỏ nhất.
Tại một buôn làng nọ, có một ngời cha và hai người con trai. Người cha mất đi để lại cho hai con trai một số gia tài (nhà cửa, trâu bò, cồng chiêng….). Hai người con không biết phân chia như thế nào cho đều nhau nên mới nhờ đến già làng chia gia tài giúp. Già làng cũng chịu thua và nhờ anh (chị) thiết kế giúp một giải thuật để chia gia tài cho hai anh em.
Giả sử rằng người cha có n món gia tài, giá trị của chúng lần lượt là v1, v2,…vn (tất cả đều là số nguyên dương). Hãy giúp già làng chia gia tài cho hai người con sao cho tổng giá trị gia tài của hai anh em chênh lệch nhau ít nhất. Có nghĩa là nesu gọi A là tổng giá trị gia tài của anh, B là tổng giá trị gia tài của người em, thì | A – B | nhỏ nhất. Có thể nhận thấy rằng để độ chênh lệch nhỏ nhất thì tổng giá trị gia tài của từng người gần với 1/2 tổng số gia tài nhất.
Ví dụ: Người cha có 5 món gia tài có giá trị lần lượt là: 3, 4, 2, 7, 5. Ta có thể chia như sau:
- Người anh (3 món): 3 + 2 + 5 = 10
- Người em (2 món): 4 + 7 = 11
- Độ chênh lệch: | 10 – 11 | = 1
Câu 1: Áp dụng kỹ thuật háu ăn (greedy) để thiết kế giải thuật chia gia tài. Tính độ phức tạp thời gian của giải thuật theo n.
Câu 2: Áp dụng kỹ thuật chia để trị thiết kế giải thuật (đệ quy) tính độ chênh lêch giá trị gia tài của hai anh em sao cho độ chênh lệch này nhỏ nhất.
