0-1 consultas de mochila

Dada una array de enteros W[] que consiste en los pesos de los artículos y algunas consultas que consisten en la capacidad C de la mochila, para cada consulta encuentre el peso máximo que podemos poner en la mochila. El valor de C no supera un cierto número entero C_MAX .

Ejemplos: 

Entrada: W[] = {3, 8, 9} q = {11, 10, 4} 
Salida: 
11 
9 
3 
Si C = 11: seleccione 3 + 8 = 11 
Si C = 10: seleccione 9 
Si C = 4: seleccione 3

Entrada: W[] = {1, 5, 10} q = {6, 14} 
Salida: 
6 
11 

Se recomienda que lea este artículo sobre la mochila 0-1 antes de intentar este problema.

Enfoque ingenuo: para cada consulta, podemos generar todos los subconjuntos de peso posibles y elegir el que tiene el peso máximo entre todos esos subconjuntos que caben en la mochila. Por lo tanto, responder a cada consulta llevará un tiempo exponencial.

Enfoque eficiente: Optimizaremos la respuesta a cada consulta mediante programación dinámica . 
La mochila 0-1 se resuelve usando 2-D DP, un estado ‘i’ para el índice actual (es decir, seleccionar o rechazar) y otro para la capacidad restante ‘R’. 
La relación de recurrencia es 

dp[i][R] = max(arr[i] + dp[i + 1][R – arr[i]], dp[i + 1][R]) 
 

Calcularemos previamente la array bidimensional dp[i][C] para cada valor posible de ‘C’ entre 1 y C_MAX en O(C_MAX*i). 
Usando este cálculo previo, podemos responder cada consulta en tiempo O (1).

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
#define C_MAX 30
#define max_arr_len 10
using namespace std;
 
// To store states of DP
int dp[max_arr_len][C_MAX + 1];
 
// To check if a state has
// been solved
bool v[max_arr_len][C_MAX + 1];
 
// Function to compute the states
int findMax(int i, int r, int w[], int n)
{
 
    // Base case
    if (r < 0)
        return INT_MIN;
    if (i == n)
        return 0;
 
    // Check if a state has
    // been solved
    if (v[i][r])
        return dp[i][r];
 
    // Setting a state as solved
    v[i][r] = 1;
    dp[i][r] = max(w[i] + findMax(i + 1, r - w[i], w, n),
                   findMax(i + 1, r, w, n));
 
    // Returning the solved state
    return dp[i][r];
}
 
// Function to pre-compute the states
// dp[0][0], dp[0][1], .., dp[0][C_MAX]
void preCompute(int w[], int n)
{
    for (int i = C_MAX; i >= 0; i--)
        findMax(0, i, w, n);
}
 
// Function to answer a query in O(1)
int ansQuery(int w)
{
    return dp[0][w];
}
 
// Driver code
int main()
{
    int w[] = { 3, 8, 9 };
    int n = sizeof(w) / sizeof(int);
 
    // Performing required
    // pre-computation
    preCompute(w, n);
 
    int queries[] = { 11, 10, 4 };
    int q = sizeof(queries) / sizeof(queries[0]);
 
    // Perform queries
    for (int i = 0; i < q; i++)
        cout << ansQuery(queries[i]) << endl;
 
    return 0;
}

// Java implementation of the approach
class GFG
{
    static int C_MAX = 30;
    static int max_arr_len = 10;
     
    // To store states of DP
    static int dp [][] = new int [max_arr_len][C_MAX + 1];
     
    // To check if a state has
    // been solved
    static boolean v[][]= new boolean [max_arr_len][C_MAX + 1];
     
    // Function to compute the states
    static int findMax(int i, int r, int w[], int n)
    {
     
        // Base case
        if (r < 0)
            return Integer.MIN_VALUE;
        if (i == n)
            return 0;
     
        // Check if a state has
        // been solved
        if (v[i][r])
            return dp[i][r];
     
        // Setting a state as solved
        v[i][r] = true;
        dp[i][r] = Math.max(w[i] + findMax(i + 1, r - w[i], w, n),
                                        findMax(i + 1, r, w, n));
     
        // Returning the solved state
        return dp[i][r];
    }
     
    // Function to pre-compute the states
    // dp[0][0], dp[0][1], .., dp[0][C_MAX]
    static void preCompute(int w[], int n)
    {
        for (int i = C_MAX; i >= 0; i--)
            findMax(0, i, w, n);
    }
     
    // Function to answer a query in O(1)
    static int ansQuery(int w)
    {
        return dp[0][w];
    }
     
    // Driver code
    public static void main (String[] args)
    {
 
        int w[] = new int []{ 3, 8, 9 };
        int n = w.length;
         
        // Performing required
        // pre-computation
        preCompute(w, n);
     
        int queries[] = new int [] { 11, 10, 4 };
        int q = queries.length;
     
        // Perform queries
        for (int i = 0; i < q; i++)
            System.out.println(ansQuery(queries[i]));
    }
}
 
// This code is contributed by ihritik

# Python3 implementation of the approach
 
import numpy as np
import sys
 
C_MAX = 30
max_arr_len = 10
 
# To store states of DP
dp = np.zeros((max_arr_len,C_MAX + 1));
 
# To check if a state has
# been solved
v = np.zeros((max_arr_len,C_MAX + 1));
 
INT_MIN = -(sys.maxsize) + 1
 
# Function to compute the states
def findMax(i, r, w, n) :
 
    # Base case
    if (r < 0) :
        return INT_MIN;
         
    if (i == n) :
        return 0;
 
    # Check if a state has
    # been solved
    if (v[i][r]) :
        return dp[i][r];
 
    # Setting a state as solved
    v[i][r] = 1;
    dp[i][r] = max(w[i] + findMax(i + 1, r - w[i], w, n),
                findMax(i + 1, r, w, n));
 
    # Returning the solved state
    return dp[i][r];
 
 
# Function to pre-compute the states
# dp[0][0], dp[0][1], .., dp[0][C_MAX]
def preCompute(w, n) :
 
    for i in range(C_MAX, -1, -1) :
        findMax(0, i, w, n);
 
 
# Function to answer a query in O(1)
def ansQuery(w) :
 
    return dp[0][w];
 
 
# Driver code
if __name__ == "__main__" :
 
    w = [ 3, 8, 9 ];
    n = len(w)
 
    # Performing required
    # pre-computation
    preCompute(w, n);
 
    queries = [ 11, 10, 4 ];
    q = len(queries)
 
    # Perform queries
    for i in range(q) :
        print(ansQuery(queries[i]));
 
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
static int C_MAX = 30;
    static int max_arr_len = 10;
     
    // To store states of DP
    static int[,] dp  = new int [max_arr_len, C_MAX + 1];
     
    // To check if a state has
    // been solved
    static bool[,] v = new bool [max_arr_len, C_MAX + 1];
     
    // Function to compute the states
    static int findMax(int i, int r, int[] w, int n)
    {
     
        // Base case
        if (r < 0)
            return Int32.MaxValue;
        if (i == n)
            return 0;
     
        // Check if a state has
        // been solved
        if (v[i, r])
            return dp[i, r];
     
        // Setting a state as solved
        v[i, r] = true;
        dp[i, r] = Math.Max(w[i] + findMax(i + 1, r - w[i], w, n),
                                        findMax(i + 1, r, w, n));
     
        // Returning the solved state
        return dp[i, r];
    }
     
    // Function to pre-compute the states
    // dp[0][0], dp[0][1], .., dp[0][C_MAX]
    static void preCompute(int[] w, int n)
    {
        for (int i = C_MAX; i >= 0; i--)
            findMax(0, i, w, n);
    }
     
    // Function to answer a query in O(1)
    static int ansQuery(int w)
    {
        return dp[0, w];
    }
     
 
    // Driver code
    public static void Main()
    {
        int[] w= { 3, 8, 9 };
        int n = w.Length;
         
        // Performing required
        // pre-computation
        preCompute(w, n);
     
        int[] queries = { 11, 10, 4 };
        int q = queries.Length;
     
        // Perform queries
        for (int i = 0; i < q; i++)
            Console.WriteLine(ansQuery(queries[i]));
    }
}
 
// This code is contributed by sanjoy_62.

<script>
 
// Javascript implementation of the approach
var C_MAX = 30
var max_arr_len = 10
 
// To store states of DP
var dp = Array.from(Array(max_arr_len), ()=>Array(C_MAX+1));
 
// To check if a state has
// been solved
var v = Array.from(Array(max_arr_len), ()=>Array(C_MAX+1));
 
// Function to compute the states
function findMax(i, r, w, n)
{
 
    // Base case
    if (r < 0)
        return -1000000000;
    if (i == n)
        return 0;
 
    // Check if a state has
    // been solved
    if (v[i][r])
        return dp[i][r];
 
    // Setting a state as solved
    v[i][r] = 1;
    dp[i][r] = Math.max(w[i] + findMax(i + 1, r - w[i], w, n),
                   findMax(i + 1, r, w, n));
 
    // Returning the solved state
    return dp[i][r];
}
 
// Function to pre-compute the states
// dp[0][0], dp[0][1], .., dp[0][C_MAX]
function preCompute(w, n)
{
    for (var i = C_MAX; i >= 0; i--)
        findMax(0, i, w, n);
}
 
// Function to answer a query in O(1)
function ansQuery(w)
{
    return dp[0][w];
}
 
// Driver code
var w = [3, 8, 9];
var n = w.length;
// Performing required
// pre-computation
preCompute(w, n);
var queries = [11, 10, 4];
var q = queries.length;
// Perform queries
for (var i = 0; i < q; i++)
    document.write( ansQuery(queries[i])+ "<br>");
 
</script>

11
9
3