fruit_feast.md

Fruit Feast, Medium

• Base on the variant of coin change.
• Notice that if there were no water condition, then we could've solved this via coin change.
• There is only 2 cases, either she drinks water or not.
• Hence we can make 2 seperate cases and then proceed via coin change. , money and sum

iterative approach

• take a carefull look on the data filling in 2d array.

Code sample

void solve() {
    int n, a, b;
    cin >> n >> a >> b;

    vvi memo = vvi(2, vi(5'000'010, 0));
    memo[0][0] = 1;

    for (int i = 0; i <= n; i++) {
        if (i >= a)
            memo[0][i] |= memo[0][i - a];
        if (i >= b)
            memo[0][i] |= memo[0][i - b];
        memo[1][i / 2] |= memo[0][i];
    }

    for (int i = 0; i <= n; i++) {
        if (i >= a)
            memo[1][i] |= memo[1][i - a];
        if (i >= b)
            memo[1][i] |= memo[1][i - b];
    }

    int ans = 0;
    for (int i = 0; i <= n; i++) {
        if (memo[0][i])
            ans = max(ans, i);
        if (memo[1][i])
            ans = max(ans, i);
    }
    cout << ans << '\n';
}

Memoization approach

• You will find similar to iterative one.

Code sample

#define MAXN 5000000
int T, A, B;
int memo[MAXN][2];

int recur(int fullness, bool used) {
    if (memo[fullness][used] > 0)
        return memo[fullness][used];
    if (fullness > T)
        return 0;
    int mx = fullness;

    mx = max(mx, recur(fullness + A, used));
    mx = max(mx, recur(fullness + B, used));

    if (!used) {
        mx = max(mx, recur(fullness / 2, true));
    }
    memo[fullness][used] = mx;
    return mx;
}

• BFS approach To be added