算法学习之 背包01问题 ， 备战leecode

来看题目


我们分析一下题目，首先我们要排序，这有助于我们得到最大的值，我们要得到一个递推公式

代码如下:

class Solution {
public:
    int maxSatisfaction(vector& satisfaction) {
        int n = satisfaction.size();
        vector> dp(n+1,vector(n+1));
        sort(satisfaction.begin(),satisfaction.end());
        int res = 0;
        for(int i = 1 ; i<= n ; i++){
            for(int j = 1 ; j <= i ; j++){
                dp[i][j] = dp[i-1][j-1] + satisfaction[i-1] * j; // 注意satisfaction 里的下标 和 dp 里的下标不一样
                if(j < i) {
                    dp[i][j] = max(dp[i-1][j],dp[i][j]);
                }
                res = max(res,dp[i][j]);
                
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20