Last Stone Weight II ใน C++

คำอธิบายปัญหา

สมมติว่ามีชิ้นหินหลายชิ้น แต่ละชิ้นมีน้ำหนักเป็นจำนวนเต็มบวก ในแต่ละรอบเราจะเลือกหินสองชิ้นมาชนกัน หากหินมีน้ำหนัก x และ y โดยที่ x <= y ผลลัพธ์จะเป็นดังนี้:

• ถ้า x = y ทั้งสองชิ้นจะถูกทำลายหมด
• ถ้า x != y หินที่มีน้ำหนัก x จะถูกทำลาย และหินที่มีน้ำหนัก y จะเหลือน้ำหนัก y-x

สุดท้ายจะเหลือหินได้มากที่สุด 1 ชิ้น เราต้องหาค่าน้ำหนักที่น้อยที่สุดของหินที่เหลือ (ถ้าไม่มีหินเหลือ ให้คืนค่า 0)

ตัวอย่าง: อินพุต [2,7,4,1,8,1] จะได้ผลลัพธ์ 1

วิธีแก้ปัญหา

ปัญหานี้สามารถลดรูปเป็นปัญหา Subset Sum (Knapsack) โดยเป้าหมายคือแบ่งหินออกเป็นสองกลุ่มที่มีผลรวมน้ำหนักใกล้เคียงกันมากที่สุด ความต่างของผลรวมน้ำหนักระหว่างสองกลุ่มนี้คือคำตอบ

1. คำนวณผลรวมน้ำหนักทั้งหมด (total)
2. กำหนดเป้าหมาย (req) = total / 2
3. ใช้ Dynamic Programming แบบ 1 มิติ (dp) ขนาด req+1 เพื่อตรวจสอบว่าสามารถสร้างผลรวมได้หรือไม่
4. dp[0] = true, ส่วนที่เหลือเป็น false
5. วนลูปผ่านหินแต่ละชิ้น และอัปเดต dp จากหลังมาหน้า
6. หาค่า reach สูงสุดที่ dp[reach] = true
7. คำตอบ = total - 2 * reach

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();
        int total = 0;
        for(int i = 0; i < n; i++) total += stones[i];
        
        int req = total / 2;
        vector<bool> dp(req + 1, false);
        dp[0] = true;
        int reach = 0;
        
        for(int i = 0; i < n; i++) {
            for(int j = req; j - stones[i] >= 0; j--) {
                dp[j] = dp[j] || dp[j - stones[i]];
                if(dp[j]) reach = max(reach, j);
            }
        }
        return total - (2 * reach);
    }
};

int main() {
    vector<int> v = {2,7,4,1,8,1};
    Solution ob;
    cout << ob.lastStoneWeightII(v);
    return 0;
}

อินพุต

[2,7,4,1,8,1]

เอาต์พุต

1