แผนการทำกำไรใน C++ (Profitable Schemes)

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

มีคน G คน และอาชญากรรมหลายอย่าง อาชญากรรม i ให้กำไร profit[i] ต้องการคน group[i] คน คนหนึ่งทำอาชญากรรมได้อย่างมาก 1 อย่าง หาจำนวน subset ของอาชญากรรมที่กำไรรวม ≥ P และคนรวม ≤ G modulo 10⁹+7

ตัวอย่าง

G=5, P=3, group=[2,2], profit=[2,3] → Output: 2

แนวทางแก้ปัญหา: 0/1 Knapsack DP

State: dp[g][p] = จำนวนวิธีใช้คน g คน ได้กำไร p (p ตัดที่ P เพราะ ≥P ถือว่าเท่ากัน)

Transition: สำหรับแต่ละอาชญากรรม (g, p) อัปเดตจากหลังไปหน้า:

for i = G-g down to 0:
    for j = P down to 0:
        dp[i+g][min(P, j+p)] += dp[i][j]

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

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

class Solution {
public:
    int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
        vector<vector<int>> dp(G+1, vector<int>(P+1, 0));
        dp[0][0] = 1;
        
        for(int k=0; k=0; i--) {
                for(int j=P; j>=0; j--) {
                    int ng = i+g, np = min(P, j+p);
                    dp[ng][np] = (dp[ng][np] + dp[i][j]) % MOD;
                }
            }
        }
        
        int ret = 0;
        for(int i=0; i<=G; i++) ret = (ret + dp[i][P]) % MOD;
        return ret;
    }
};

ความซับซ้อน

• เวลา: O(n × G × P) โดย n = จำนวนอาชญากรรม
• พื้นที่: O(G × P)