Problema P2079: Jantar com Velas

O objetivo é ajudar Xiao Ming a escolher pratos para um jantar romântico com Xiao Hong, dentro de um orçamento limitado. Ele deseja maximizar o grau de satisfação de Xiao Hong, respeitando duas restrições:

• O custo total dos pratos não pode exceder o valer disponível V.
• A soma total de satisfação de Xiao Ming deve ser maior ou igual a zerro.

Cada prato tem três atributos:

• Ci: preço do prato.
• X_i: nível de satisfação de Xiao Ming.
• Y_i: nível de satisfação de Xiao Hong.

Os valores de satisfação podem ser negativos, representando desagrado. ### Entrada

A primeira linha contém dois intieros N (número de pratos) e V (orçamento máximo). As próximas N linhas fornecem os valores Ci, Xi, Yi para cada prato.

Saída

Um número inteiro representando a máxima satisfação possível de Xiao Hong, sob a condição de que a satisfação total de Xiao Ming seja ≥ 0. Se nenhum resultado válido for possível, retorne -1.

Exemplo

Entrada:
4 10
5 -1 3
2 2 2
11 -5 100
3 -3 10

Saída:
5

Abordagem

Este problema é uma variação da mochila dinâmica com duas dimensões: custo e satisfação de Xiao Ming. A ideia é usar programação dinâmica onde:

• dp[c][s] armazena a máxima satisfação de Xiao Hong possível ao gastar c unidades e ter uma satisfação acumulada de Xiao Ming igual a s.
• Dado que Xi pode variar entre -5 e 5, o intervalo de satisfação de Xiao Ming será de -500 a +500. Para evitar índices negativos, usamos um deslocamento de 500.

Código em C++

#include <bits/stdc++.h>
using namespace std;

const int MAX_V = 500;
const int OFFSET = 500;
const int MAX_SAT = 1000;

int n, budget;
int dp[MAX_V + 1][MAX_SAT + 1];

int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch != '-' && !isdigit(ch)) ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main() {
    memset(dp, -1, sizeof(dp));
    n = read(); budget = read();
    dp[0][OFFSET] = 0;  // Inicializa com satisfação zero de Xiao Hong, e posição central no eixo de satisfação de Xiao Ming.

    for (int i = 0; i < n; ++i) {
        int cost = read(), x_sat = read(), y_sat = read();

        for (int c = budget; c >= cost; --c) {
            for (int sat = 0; sat <= MAX_SAT; ++sat) {
                if (dp[c - cost][sat] == -1) continue;
                int new_sat = sat + x_sat;
                if (new_sat < 0 || new_sat > MAX_SAT) continue;
                if (dp[c][new_sat] < dp[c - cost][sat] + y_sat) {
                    dp[c][new_sat] = dp[c - cost][sat] + y_sat;
                }
            }
        }
    }

    int result = -1;
    for (int c = 0; c <= budget; ++c) {
        for (int sat = OFFSET; sat <= MAX_SAT; ++sat) {
            if (dp[c][sat] != -1) {
                result = max(result, dp[c][sat]);
            }
        }
    }

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

Este algoritmo utiliza programação dinâmica com otimização de espaço e tempo, garantindo eficiência mesmo para os limites superiores do problema.