879. Profitable Schemes(背包计数)

Bertha 。 2022-02-23 10:26 125阅读 0赞

[https://leetcode.com/problems/profitable-schemes/][https_leetcode.com_problems_profitable-schemes]

题意：有G个人，有n种犯罪方式每种犯罪方式都可以获得profit\[i\]的利益，每种犯罪方式都需要group\[i\]个人，要使获得利益大于等于P，求有多少种方式。

思路：G个人等价于背包的容量限制。设dp\[i\]\[j\]\[k\]表示前i种犯罪方式，使用j个人，获得k的利益的方案数。由于第i种犯罪方式只和第i-1种有关，所以可以滚动成2维dp，dp\[j\]\[k\]即可，不过需要注意的是j,k需要逆推。

dp\[j\]\[k\]+=dp\[j-group\[i\]\] \[k-profit\[i\]\]；

代码：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+7;
    typedef long long ll;
    class Solution {
    public:
        int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
            int dp[105][10005];
            memset(dp,0,sizeof(dp));
            int n = profit.size();
            int mod = 1e9+7;
            int tot=0;
            for(auto &t:profit){
              tot+=t;
            }
            dp[0][0]=1;
            for(int i=0;i<n;i++){
              for(int j=G;j>=group[i];j--){
                for(int k=tot;k>=profit[i];k--){
                  dp[j][k]+=dp[j-group[i]][k-profit[i]];
                  dp[j][k]%=mod;
                }
              }
            }
            int ans=0;
            for(int k=P;k<=tot;k++){
              for(int i=1;i<=G;i++){
                ans=(ans+dp[i][k])%mod;
              }
            }
            return ans;
        }
    };

[https_leetcode.com_problems_profitable-schemes]: https://leetcode.com/problems/profitable-schemes/

发表评论取消回复

表情：

评论列表（有 0 条评论，125人围观）

还没有评论，来说两句吧...

相关阅读

相关数字组合（背包计数）

2046: 数字组合时间限制: 0 Sec 内存限制: 128 MB 提交: 2 解决: 1 \[ [提交][Link 1]\]\[ [状态][Link 2]\

柔情只为你懂/ 2024年02月18日 14:36/ 0 赞/ 4 阅读

相关 879. 盈利计划

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。第 i 种工作会产生 profit\[i\] 的利润，它要求 group\[i\] 名成员共同参与。如果成员参与了

系统管理员/ 2022年10月05日 13:52/ 0 赞/ 113 阅读

相关 LeetCode 879. 盈利计划

[879. 盈利计划][879.] 本题与经典背包问题非常相似。两者不同点在于经典背包问题只有一种容量限制，而本题却有两种限制：集团员工人数上限 n，以及工作产生的利润下限

水深无声/ 2022年10月05日 12:51/ 0 赞/ 109 阅读

相关算法——背包问题 01背包+完全背包+多重背包

01背包：https://biancheng.love/problem/51/index 有n 种不同的物品，每个物品有两个属性，weight重量，value 价值，现在给一

ゞ浴缸里的玫瑰/ 2022年06月06日 10:41/ 0 赞/ 261 阅读

相关 content:// scheme 和 file:// scheme

path 转 Uri (content://) / 根据file path 获取content:// @param context @param filePat

水深无声/ 2022年06月02日 06:05/ 0 赞/ 336 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 299 阅读

相关背包问题-01背包，完全背包，多重背包

背包问题-01背包，完全背包，多重背包 -------------------- 01背包：概念：有Goods\_Num件物品，MAX\_V

太过爱你忘了你带给我的痛/ 2022年05月14日 09:23/ 0 赞/ 251 阅读

相关 879. Profitable Schemes(背包计数)

[https://leetcode.com/problems/profitable-schemes/][https_leetcode.com_problems_profitab

Bertha 。/ 2022年02月23日 10:26/ 0 赞/ 126 阅读

相关 Data.URI.scheme

<!DOCTYPE html> <html> <body> <!-- Data URI scheme是在RFC2397中定义的，目的是将

比眉伴天荒/ 2021年11月29日 18:02/ 0 赞/ 188 阅读

相关 P3009 [USACO11JAN]利润Profits

题目描述 The cows have opened a new business, and Farmer John wants to see how well they

向右看齐/ 2021年11月26日 07:36/ 0 赞/ 186 阅读