暑假算法7.28，Day27

暑假算法7.28，Day27

01背包

第一题

分割等和子集

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int & num : nums)
            sum += num;
        if(sum % 2 == 1) return false;

        int target = sum / 2;
        
        vector<int> dp(target + 1, 0);
        for(int i = 0; i < nums.size(); i++)
            for(int j = target; j >= nums[i]; j--){
                dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
            }

        if(dp[target] == target) return true;
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第二题

目标和

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0,bagWeight;
        for(int i:nums)
            sum+=i;
        if(sum<abs(target)) {
            return 0;
        }
        if((target+sum)%2) {
            return 0;
        }
        bagWeight=(target+sum)>>1;
        vector<int> dp(bagWeight+1,0);
        dp[0]=1;
        for(int i=0;i<nums.size();++i){
            for(int j=bagWeight;j>=nums[i];--j){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[bagWeight];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

第三题

盈利计划

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int len = group.size();
        vector<vector<int>> dp (minProfit+1, vector<int>(n+1,0));
        dp[0][0] = 1;
        for(int i = 0; i<len; i++){
            for(int j = minProfit; j>=0; j--){
                for(int k = n; k>=0; k--){
                    if(dp[j][k]!=0 && k+group[i]<=n){
                        int tmp_j = min(minProfit, j+profit[i]);
                        dp[tmp_j][k+group[i]] += dp[j][k];
                        dp[tmp_j][k+group[i]] %= 1000000007;
                    }
                }
            }
        }
        int sum = 0;
        for(int k = 0; k<n+1; k++){
            sum += dp[minProfit][k];
            sum %= 1000000007;
        }
        return sum;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26