ข้อ 1. วิธีของคุณ<คิดด้วยคน>เป็นวิธีที่ดีมากอันนึงแต่ไม่สามารถรับประกันได้ว่า
จะได้คำตอบที่ถูกต้องเสมอไป ตัวอย่างเช่น ถ้าเรามีก้อนหิน 8 ก้อนซึ่งมีน้ำหนัก
10, 9, 8, 8, 8, 7, 7, 6 ถ้าแบ่งตามวิธีดังกล่าวจะได้
10 + 9 + 8 = 27 กับ 8 + 8 + 7 + 7 + 6 = 36
ในขณะที่เราสามารถทำได้ดีกว่านั้นเช่น
9 + 8 + 8 + 6 = 31 กับ 10 + 8 + 7 + 7 = 32
จริงๆแล้ววิธีนี้จะมีปัญหาตั้งแต่ช่วงแรกแล้วเพราะการตรวจสอบว่ามี subset ใดที่มี
ผลรวมเท่ากับ x/2 เป็นเรื่องยากมาก แต่เราก็แก้ปัญหานี้ได้ง่ายๆโดยใช้ algorithm
ของช่วงสองตั้งแต่เริ่มเลย โดยไม่สนใจว่าจะมี subset ใดที่มีผลรวมเท่ากับ x/2
หรือไม่ ผมเดาเอาว่าปัญหาข้อนี้น่าจะเป็น NP-hard problem นะครับ
ข้อ 2. ผมไม่แน่ใจว่าผมเข้าใจวิธี "กิน" ถูกต้องรึเปล่า แต่ถ้า "กิน" แบบที่ผมเข้าใจ
จะได้คำตอบเท่ากับของคุณ gon คือ
้m
๙ x
้n
๙ ครับผม
