1. Seleción de máximo un elemento por grupo

Código de implementación

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

const int MAX = 1000;
int dp[MAX][MAX];

int main() {
    int tipos, capacidad;
    cin >> tipos >> capacidad;
    
    for(int grupo = 1; grupo <= tipos; grupo++) {
        int elementos;
        cin >> elementos;
        for(int c = capacidad; c >= 0; c--) {
            for(int obj = 0; obj < elementos; obj++) {
                int volumen, valor;
                cin >> volumen >> valor;
                if(c >= volumen) {
                    dp[grupo][c] = max(dp[grupo][c], dp[grupo-1][c-volumen] + valor);
                }
            }
        }
    }
    cout << dp[tipos][capacidad];
    return 0;
}

2. Selección de mínimo un elemento por grupo

Código de implementación

#include <iostream>
#include <cstring>
using namespace std;

const int MAX = 1000;
int dp[MAX][MAX];

int main() {
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    
    int grupos, capacidad;
    cin >> grupos >> capacidad;
    
    for(int g = 1; g <= grupos; g++) {
        int objetos;
        cin >> objetos;
        for(int obj = 0; obj < objetos; obj++) {
            int vol, val;
            cin >> vol >> val;
            for(int c = capacidad; c >= vol; c--) {
                if(dp[g][c-vol] != -1) 
                    dp[g][c] = max(dp[g][c], dp[g][c-vol] + val);
                if(dp[g-1][c-vol] != -1)
                    dp[g][c] = max(dp[g][c], dp[g-1][c-vol] + val);
            }
        }
    }
    cout << dp[grupos][capacidad];
    return 0;
}

3. Selección libre por grupo

Código de implementación

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

const int MAX = 1000;
int dp[MAX][MAX];

int main() {
    int grupos, capacidad;
    cin >> grupos >> capacidad;
    
    for(int g = 1; g <= grupos; g++) {
        int objetos;
        cin >> objetos;
        // Copiar resultados anteriores
        for(int c = 0; c <= capacidad; c++) 
            dp[g][c] = dp[g-1][c];
            
        for(int obj = 0; obj < objetos; obj++) {
            int vol, val;
            cin >> vol >> val;
            for(int c = capacidad; c >= vol; c--) {
                if(dp[g][c-vol] != -1)
                    dp[g][c] = max(dp[g][c], dp[g][c-vol] + val);
                if(dp[g-1][c-vol] != -1)
                    dp[g][c] = max(dp[g][c], dp[g-1][c-vol] + val);
            }
        }
    }
    cout << dp[grupos][capacidad];
    return 0;
}

Implemetnación combinada

Código completo

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 200;
const int MAX_M = 200;
int dp[MAX_N][MAX_M];

int main() {
    int n, m;
    while(cin >> n >> m) {
        memset(dp, -1, sizeof(dp));
        memset(dp[0], 0, sizeof(dp[0]));
        
        for(int i = 1; i <= n; i++) {
            int num, opcion;
            cin >> num >> opcion;
            
            int volumenes[num], valores[num];
            for(int j = 0; j < num; j++) {
                cin >> volumenes[j] >> valores[j];
            }
            
            if(opcion == 0) { // Máximo 1
                for(int j = 0; j < num; j++) {
                    for(int k = m; k >= volumenes[j]; k--) {
                        if(dp[i-1][k-volumenes[j]] != -1) {
                            dp[i][k] = max(dp[i][k], dp[i-1][k-volumenes[j]] + valores[j]);
                        }
                    }
                }
            }
            else if(opcion == 1) { // Mínimo 1
                memcpy(dp[i], dp[i-1], sizeof(dp[i-1]));
                for(int j = 0; j < num; j++) {
                    for(int k = m; k >= volumenes[j]; k--) {
                        if(dp[i-1][k-volumenes[j]] != -1) {
                            dp[i][k] = max(dp[i][k], dp[i-1][k-volumenes[j]] + valores[j]);
                        }
                    }
                }
            }
            else if(opcion == 2) { // Libre
                memcpy(dp[i], dp[i-1], sizeof(dp[i-1]));
                for(int j = 0; j < num; j++) {
                    for(int k = m; k >= volumenes[j]; k--) {
                        if(dp[i][k-volumenes[j]] != -1) {
                            dp[i][k] = max(dp[i][k], dp[i][k-volumenes[j]] + valores[j]);
                        }
                    }
                }
            }
        }
        cout << dp[n][m] << endl;
    }
    return 0;
}