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

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

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

来看题目


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

代码如下:

class Solution {
public:int maxSatisfaction(vector<int>& satisfaction) {int n = satisfaction.size();vector<vector<int>> dp(n+1,vector<int>(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;}
};