Aiuto Greedy Santa

Aiuto
1

Ciao, ho scritto un codice per Greedy Santa, ottengo corrette tutte le subtasks tranne 2, probabilmente mi perdo qualcosa di ovvio, ma non lo trovo.
Consigli?

#include <stdio.h>
#include <assert.h>
#include <iostream>
#define MAXN 100000
using namespace std;

int N, B, i,j;
int V,sum=0;
int arr[MAXN] { 0 };
int budget=0;
bool check = true;

int main() {

    cin >> N >> B;
    for(j=0; j<N; j++){
        cin >> V;
        sum+=V;
        arr[V]=1;
        for(i=B; i!=-1; i--){
            if(arr[i]==1&&i!=V)
                arr[i+V]=1;
    }
    }
    j=0;
    if(sum<=B)
    budget = sum;
    else
    for(i=0; check; i++){
        if(arr[B+i]==1){
            budget=B+i;
            break;
        }
    }

    printf("%d\n", budget);
    return 0;
}
2

Un caso che non consideri è quando ci sono più regali dello stesso prezzo.
Input:

4 7
2 2 2 2

output:
8
Se ho capito bene utilizzi “arr” per segnarti se sei arrivato a quella determinata somma, quindi ti conviene mettere a vero il valore appena letto solo dopo aver aggiornato le somme raggiungibili. Fatto ciò non dovresti aver altri problemi.

2 Mi Piace