01背包恰好装满问题

周赛遇到的LC.2915
https://leetcode.cn/problems/length-of-the-longest-subsequence-that-sums-to-target/description/
相当于01背包模型加上了一个背包恰好装满时取得的最大值

首先回顾普通的01背包

for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {
        f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}

状态划分

在普通的01背包中，因为不要求恰好装满，状态均初始化为0，代表的是背包为空时所包含的物体价值为0，所有没装满的状态都是有效状态。
在恰好条件下，需要认为背包没有恰好装满的话为无效状态，只有恰好装满时候才是有效状态。定义无效状态值为负无穷以便区分，通过判断f[v]的值是否为负无穷来判断背包是否装满。

状态转移

与01背包状态转移方程一致，但有效状态只由有效状态推出

#define INF 0x80000000
class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n = nums.size(), m = target;
        int ans = -1;
        vector<int> f(target + 1, INF);
        f[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = target; j >= nums[i - 1]; j--) {
                f[j] = max(f[j], f[j - nums[i - 1]] + 1);
                if (f[j] < 0) {
                    f[j] = INF;
                }
            }
        }
        
        if (f[target] > 0) {
            return f[target];
        }
        
        return -1;
    }
};