รูปแบบการทำกำไรใน C++

สมมติว่ามีแก๊งค์ที่มีคนจีและรายการอาชญากรรมต่างๆ ที่พวกเขาสามารถก่อได้ อาชญากรรมครั้งที่ i สร้างผลกำไรมูลค่ากำไร[i] และต้องการให้สมาชิกแก๊งค์[i]เข้าร่วม

หากสมาชิกแก๊งมีส่วนร่วมในอาชญากรรมอย่างใดอย่างหนึ่ง ว่าเขาไม่สามารถมีส่วนร่วมในอาชญากรรมอื่นได้ ตอนนี้ ให้เรากำหนดรูปแบบการทำกำไรของกลุ่มย่อยของอาชญากรรมเหล่านี้ที่สร้างผลกำไรอย่างน้อย P และจำนวนสมาชิกทั้งหมดที่เข้าร่วมในกลุ่มย่อยของอาชญากรรมนั้นมากที่สุด G

เราต้องหาว่าสามารถเลือกแบบแผนได้กี่แบบ? คำตอบอาจมีขนาดใหญ่มาก ให้คืนค่าเป็นโมดูล 10^9 + 7.

ดังนั้น หากอินพุตเป็นเหมือน G =5, P =3 และ group =[2,2], profit =[2,3] ผลลัพธ์จะเป็น 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ยกเลิก :=0

• กำหนดขนาดอาร์เรย์ 2 มิติหนึ่ง dp (G + 1) x (P + 1)

• dp[0, 0] :=1

• สำหรับการเริ่มต้น k :=0 เมื่อ k <ขนาดของกลุ่ม ให้อัปเดต (เพิ่ม k ขึ้น 1) ให้ทำ -

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

  • สำหรับการเริ่มต้น i :=G - g เมื่อ i>=0, อัปเดต (ลด i โดย 1) ทำ -

    • สำหรับการเริ่มต้น j :=P เมื่อ j>=0, อัปเดต (ลด j โดย 1) do−

      • dp[i + g, ค่าต่ำสุดของ P และ j + p]

      • dp[i + g, ค่าต่ำสุดของ P และ j + p]

• สำหรับการเริ่มต้น i :=0 เมื่อ i <=G อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

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

  • ret :=ret mod m

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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));
}

อินพุต

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

ผลลัพธ์

2