Lược đồ có lợi trong C ++

Giả sử có một băng nhóm với người G và một danh sách các tội ác khác nhau mà họ có thể phạm phải. Tội phạm thứ i tạo ra lợi nhuận giá trị lợi nhuận [i] và yêu cầu các thành viên băng nhóm [i] tham gia.

Nếu một thành viên băng đảng tham gia vào một tội phạm, anh ta không thể tham gia vào một tội phạm khác. Bây giờ, chúng ta hãy xác định kế hoạch sinh lợi bất kỳ tập hợp con nào trong số các tội phạm này tạo ra lợi nhuận ít nhất là P và tổng số thành viên tham gia vào tập hợp con tội phạm đó nhiều nhất là G.

Chúng ta phải tìm xem có bao nhiêu phương án có thể được chọn? Câu trả lời có thể rất lớn, Vì vậy, hãy trả lại nó theo mô-đun 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như G =5, P =3 và nhóm =[2,2], lợi nhuận =[2,3], thì đầu ra sẽ là 2

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0

• Xác định một dp mảng 2D có kích thước (G + 1) x (P + 1)

• dp [0, 0]:=1

• để khởi tạo k:=0, khi k

  • p:=profit [k], g:=group [k]

  • để khởi tạo i:=G - g, khi i> =0, cập nhật (giảm i đi 1), thực hiện -

    • để khởi tạo j:=P, khi j> =0, cập nhật (giảm j đi 1), do−

      • dp [i + g, tối thiểu là P và j + p]

      • dp [i + g, tối thiểu là P và j + p]

• để khởi tạo i:=0, khi i <=G, cập nhật (tăng i lên 1), thực hiện -

  • ret:=ret + dp [i, P]

  • ret:=ret mod m

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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> &lprofit) {
      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];
         int 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;
   }
};
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