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;
}
};