• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode879.盈利计划|ProfitableSchemes

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址: https://www.cnblogs.com/strengthen/p/10601257.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

There are G people in a gang, and a list of various crimes they could commit.

The i-th crime generates a profit[i] and requires group[i] gang members to participate.

If a gang member participates in one crime, that member can't participate in another crime.

Let's call a profitable scheme any subset of these crimes that generates at least Pprofit, and the total number of gang members participating in that subset of crimes is at most G.

How many schemes can be chosen?  Since the answer may be very large, return it modulo 10^9 + 7

Example 1:

Input: G = [2,3]
Output: 2
Explanation: 
To make a profit of at least 3, the gang could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.

Example 2:

Input: G = [6,7,8]
Output: 7
Explanation: 
To make a profit of at least 5, the gang could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2). 

Note:

  1. 1 <= G <= 100
  2. 0 <= P <= 100
  3. 1 <= group[i] <= 100
  4. 0 <= profit[i] <= 100
  5. 1 <= group.length = profit.length <= 100

帮派里有 G 名成员,他们可能犯下各种各样的罪行。

第 i 种犯罪会产生 profit[i] 的利润,它要求 group[i] 名成员共同参与。

让我们把这些犯罪的任何子集称为盈利计划,该计划至少产生 P 的利润。

有多少种方案可以选择?因为答案很大,所以返回它模 10^9 + 7 的值。 

示例 1:

输入:G = 5, P = 3, group = [2,2], profit = [2,3]
输出:2
解释: 
至少产生 3 的利润,该帮派可以犯下罪 0 和罪 1 ,或仅犯下罪 1 。
总的来说,有两种方案。

示例 2:

输入:G = 10, P = 5, group = [2,3,5], profit = [6,7,8]
输出:7
解释:
至少产生 5 的利润,只要他们犯其中一种罪就行,所以该帮派可以犯下任何罪行 。
有 7 种可能的计划:(0),(1),(2),(0,1),(0,2),(1,2),以及 (0,1,2) 。 

提示:

  1. 1 <= G <= 100
  2. 0 <= P <= 100
  3. 1 <= group[i] <= 100
  4. 0 <= profit[i] <= 100
  5. 1 <= group.length = profit.length <= 100

Runtime: 1032 ms
Memory Usage: 18.8 MB
 1 class Solution {
 2     func profitableSchemes(_ G: Int, _ P: Int, _ group: [Int], _ profit: [Int]) -> Int {
 3         var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:G + 1),count:P + 1)
 4         dp[0][0] = 1
 5         var res:Int = 0
 6         var mod:Int = Int(1e9 + 7)
 7         for k in 0..<group.count
 8         {
 9             var g:Int = group[k]
10             var p:Int = profit[k]
11             for i in stride(from:P,through:0,by:-1)
12             {
13                 for j in stride(from:G - g,through:0,by:-1)
14                 {
15                     dp[min(i + p, P)][j + g] = (dp[min(i + p, P)][j + g] + dp[i][j]) % mod
16                 }
17             }
18         }
19         for x in dp[P]
20         {
21             res = (res + x) % mod
22         }
23         return res
24     }
25 }

Runtime: 1192 ms
Memory Usage: 19.4 MB
 1 class Solution {
 2     func profitableSchemes(_ G: Int, _ P: Int, _ group: [Int], _ profit: [Int]) -> Int {
 3         guard G >= 1 && G <= 100 && P >= 0 && P <= 100 && group.count >= 1 && group.count <= 100 && group.count == profit.count else {
 4             return 0
 5         }
 6         let mod = Int(1e9 + 7)
 7         var crimePlanCount = Array(repeating: Array(repeating: 0, count: G + 1), count: P + 1)
 8         crimePlanCount[0][0] = 1
 9         for (index, groupValue) in group.enumerated() {
10             let profitValue = profit[index]
11             for p in stride(from: P, through: 0, by: -1) {
12                 for g in stride(from: G, through: 0, by: -1) {
13                     if groupValue + g > G || crimePlanCount[p][g] == 0 {
14                         continue
15                     }
16                     let targetProfit = min(P, profitValue + p)
17                     let targetGroup = groupValue + g
18                     crimePlanCount[targetProfit][targetGroup] += crimePlanCount[p][g]
19                     crimePlanCount[targetProfit][targetGroup] %= mod
20                 }
21             }
22         }
23         var result = 0
24         for count in crimePlanCount[P] {
25             result += count
26         }
27         return result % mod
28     }
29 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
iOS开发(swift):页面跳转传值发布时间:2022-07-13
下一篇:
OC语言中的标记#pragma mark 在swift中标记方法发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap