如何找到等于和的子序列的最大子集的大小

Question

我有来自hackerearth的this问题

给定一组N个整数，C卡和S和。每张卡可用于将给定数组中的整数递增或递减1.查找给定数组中是否有任何子集（在使用任何no.of卡之前/之前）和S。

输入格式

第一行输入包含一个表示no的整数T.测试用例。每个测试用例有2行输入。每个测试用例的第一行有三个整数N（数组的大小），S（子集和）和C（卡的数量）。每个测试用例的第二行具有由空格分隔的数组（a1至aN）的N个整数。

约束

1 <= T <= 100 1 <= N <= 100 1 <= S <= 10000 0 <= C <= 100 1 <= ai <= 100

输出格式

如果存在具有给定总和的子集，则打印为TRUE，否则打印为FALSE。

因此，这基本上是子集和问题的变体，但是我们需要找到从S序列到index的最大子集，而不是找出具有N-1和的s的最大子集，并将其长度与C进行比较。我们的C值，看它是否更大。如果是，那么我们有足够的元素来使用我们的

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, S, C;


int checkSum(int index, int s, vector<int>& a, vector< vector<int> >& dP) {

    if (dP[index][s] != -1)
        return dP[index][s];

    int maxNums = 0;    // size of maximum subset array

    for (int i = index; i < N; i++) {

        int newSum = s - a[i];
        int l = 0;

        if (newSum == 0) {
            l = 1;
        } if (newSum > 0) {

            if (i < (N-1)) {    // only if we can still fill up sum
                l = checkSum(i + 1, newSum, a, dP);

                if (l > 0)      // if it is possible to create this sum
                    l++;        // include l in it
            } else {
                // l stays at 0 for there is no subset that can create this sum
            }

        } else {
            // there is no way to create this sum, including this number, so skip it;
            if (i == (N-1))
                break;      // don't go to the next level

            // and l stays at 0
        }

        if (l > maxNums) {
            maxNums = l;
        }
    }

    dP[index][s] = maxNums;
    return maxNums;
}


int main() {

    int t;
    cin >> t;

    while (t--) {
        cin >> N >> S >> C;
        vector<int> a(N);

        for (int i = 0; i < N; i++)
            cin >> a[i];

        vector< vector<int> > dP(N, vector<int>(S + C + 2, -1));

        bool possible = false;

        for (int i = 0; i <= C; i++) {
            int l = checkSum(0, S-i, a, dP);
            int m = checkSum(0, S+i, a, dP);

            if ( (l > 0 && l >= i) || (m > 0 && m >= i) ) {

                cout << "TRUE" << endl;
                possible = true;
                break;
            }

        }

        if (!possible)
            cout << "FALSE" << endl;
    }

    return 0;
}

卡修改总和，然后我们打印出我们的答案。这是我的代码

else

所以基本上，0表示不可能从元素索引到N-1创建一个等于s的子集，-1表示我们还没有计算它。并且任何其他值表示总计为s的最大子集的大小。此代码未通过所有测试用例。怎么了？

Answer 1

你错过了以下一行中的} if (newSum > 0) {

maxNums

这使得您的程序在某些情况下通过l更新l >= i之前有意想不到的早期休息。

例如，N = 1，S = 5，C = 0，a = {5}

---

潜在的逻辑问题

你限制了没有。用于不超过子集大小的卡，而问题永远不会表明您不能将多张卡应用于相同的整数。

我的意思是m >= i和if ( (l > 0 && l >= i) || (m > 0 && m >= i) ) { in

S-C..S+C

Answer 2

似乎你有逻辑缺陷。

你需要找到最短的子集（总和在C范围内）并将其大小与qazxswpoi进行比较。如果子集较短，则可以进行所需的总和。