3181. 执行操作可获得的最大总奖励 II

题目描述：

有n个物品，每个物品的价值是ar[i]，一个物品只能拿一次。最开始你的总奖励sum是0，你可以进行任意次操作，每次操作都可以选择任意一个未被选择过的物品，而且必须满足sum < ar[i]，获得这个物品后也将获得它的价值，即sum += ar[i]，求总奖励最大可能是多少

• easy版 n<=2000，ar[i] <= 2000
• hard版 n <= 50000, ar[i] <= 50000

思路：

首先，我们能发现，如果取了一个价值高的物品，那比它小的物品的价值都拿不了，所以肯定是从小的开始取，先对ar数组进行排序

很容易发现这个题和01背包有点像

dp[i][j]表示前 i 个物品，是否存在一种方案能使总奖励为 j

转移方程就很好想:

• 不选第 i 个物品： dp[i][j] |= dp[i - 1][j]

• 选第 i 个物品：dp[i][j] |= dp[i -1][j - tr[i]] ,j - tr[i] >= 0 && j - tr[i] > tr[i]

所以答案只需要从后往前遍历，遇到第一个1就输出

这样的复杂度是O(n * m)

class Solution {
public:
    int dp[2005][4005];
    int maxTotalReward(vector<int>& tr) {
        sort(tr.begin(), tr.end());
        int n = tr.size();
        dp[0][0] = 1;
        for(int i = 1; i <= n; ++i){
            for(int j = 0; j <= 4000; ++j){
                dp[i][j] |= dp[i - 1][j];
                if(j - tr[i - 1] >= 0 && j < 2 * tr[i - 1]){
                    dp[i][j] |= dp[i - 1][j - tr[i - 1]];  
                }
            }
        }
        for(int i = 4000; i >= 0; --i){
            if(dp[n][i]){
                return i;
            }
        }
        return 0;
    }
};

对于hard版，时间会T，要想办法优化一下

再仔细分析一下我们的状态转移方程，可以发现，第一维度可以用滚动数组滚掉

再看第二维度，可以发现其实是取了dp数组中下标范围为tr[i]<=j<2*tr[i]的数据，与下标范围为0<=j<tr[i]的数据进行了或操作

可以看成将dp数组中长度为tr[i]的一段连续的数据，与dp数组中左侧的另一段长度为tr[i]的连续数据进行逐位或操作，这样的操作可以用bitset进行代替

由于bitset的特性，下标是从右往左计算的，所以先 b<<(b.size() - tr[i])，得到前半段长度为tr[i]的数据，后半段全是0，再右移b.size() - 2 * tr[i]长度，得到了中间是长度为tr[i]的数据，左右两段都是0，正好和原先的b对上了，二者取或即得到答案

复杂度是O(n * m / 32)

class Solution {
public:
    int maxTotalReward(vector<int>& tr) {
        sort(tr.begin(), tr.end());
        int n = tr.size();
        bitset<100000>b(1);
        for(int x : tr){
            b |= b << (100000 - x) >> (100000 - 2 * x);
        }
        for(int i = 100000 - 1; i >= 0; --i){
            if(b.test(i)){
                return i;
            }
        }
        return 0;
    }
};