Kế hoạch lợi nhuận trong C++

Có G thành viên băng, danh sách tội phạm: tội i mang lại profit[i] và cần group[i] thành viên. Mỗi thành viên chỉ tham gia một tội. Kế hoạch lợi nhuận là tập con tội phạm với tổng profit ≥ P và tổng group ≤ G. Đếm số kế hoạch modulo 10^9+7.

Ví dụ: G=5, P=3, group=[2,2], profit=[2,3] → 2.

Giải thuật

1. DP 2D: dp[i][j] = số cách dùng i thành viên đạt profit j (j capped tại P).
2. Khởi tạo dp[0][0] = 1.
3. Duyệt từng tội k: p=profit[k], g=group[k]. Cập nhật dp ngược (i từ G-g xuống 0, j từ P xuống 0):
   • dp[i+g][min(P, j+p)] += dp[i][j].
4. Kết quả = sum(dp[i][P]) cho i=0..G.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
public:
    int profitableSchemes(int G, int P, vector<int> &group, vector<int> &profit) {
        int ret = 0;
        vector<vector<int>> dp(G + 1, vector<int>(P + 1));
        dp[0][0] = 1;
        for (int k = 0; k < group.size(); k++) {
            int p = profit[k], g = group[k];
            for (int i = G - g; i >= 0; i--)
                for (int j = P; j >= 0; j--) {
                    dp[i + g][min(P, j + p)] += dp[i][j];
                    dp[i + g][min(P, j + p)] %= m;
                }
        }
        for (int i = 0; i <= G; i++) { ret += dp[i][P]; ret %= m; }
        return ret;
    }
};
int main(){
    Solution ob;
    vector<int> v = {2,2}, v1 = {2,3};
    cout << (ob.profitableSchemes(5,3,v, v1));
}

Đầu vào

5, 3, [2,2], [2,3]

Đầu ra

2