c++ - 如何找到等于总和的子序列的最大子集的大小

Question

我有this来自hackerearth的问题

Given an array of N integers, C cards and S sum. Each card can be used either to increment or decrement an integer in the given array by 1. Find if there is any subset (after/before using any no.of cards) with sum S in the given array.

Input Format

First line of input contains an integer T which denotes the no. of testcases. Each test case has 2 lines of input. First line of each test case has three integers N(size of the array), S(subset sum) and C(no. of cards). Second line of each test case has N integers of the array(a1 to aN) seperated by a space.

Constraints

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

Output Format

Print TRUE if there exists a subset with given sum else print FALSE.

所以这基本上是子集求和问题的一个变体，但是我们需要从序列 index 中找到最大的子集，而不是找出一个给定的子集是否存在和 S 到具有 s 值的 N-1 并将它的长度与我们的 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;
}

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

Answer 1

你在下一行中遗漏了一个else

} if (newSum > 0) {

在某些情况下，这会使您的程序在 l 更新 maxNums 之前意外提前中断。

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

---

潜在的逻辑问题

您已限制编号。使用的卡片数量不得超过子集大小，而问题从未说明您不能将多张卡片应用于相同的整数。

我的意思是 l >= i 和 m >= i 在

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