Mochila con Pesos grandes

Dada una mochila con capacidad C y dos arrays w[] y val[] que representan los pesos y valores de N elementos distintos, la tarea es encontrar el valor máximo que puede poner en la mochila. Los artículos no se pueden romper y un artículo con peso X ocupa X capacidad de la mochila.

Ejemplos: 

Entrada: w[] = {3, 4, 5}, val[] = {30, 50, 60}, C = 8 
Salida: 90 
Tomamos los objetos ‘1’ y ‘3’. 
El valor total que obtenemos es (30 + 60) = 90. 
El peso total es 8, por lo que cabe en la capacidad dada

Entrada: w[] = {10000}, val[] = {10}, C = 100000 
Salida: 10  

Enfoque: El tradicional y famoso problema de la mochila 0-1 se puede resolver en tiempo O(N*C), pero si la capacidad de la mochila es enorme, entonces no se puede hacer una array 2D N*C. Por suerte, se puede solucionar redefiniendo los estados de la dp. 
Echemos un vistazo a los estados del DP primero.
dp[V][i] representa el subconjunto de peso mínimo del subarreglo arr[i…N-1] requerido para obtener un valor de al menos V . La relación de recurrencia será:
 

dp[V][i] = min(dp[V][i+1], w[i] + dp[V – val[i]][i + 1]) 
 

Entonces, para cada V desde 0 hasta el valor máximo de V posible, intente encontrar si la V dada se puede representar con la array dada. La V más grande que se puede representar se convierte en la respuesta requerida.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define V_SUM_MAX 1000
#define N_MAX 100
#define W_MAX 10000000
 
// To store the states of DP
int dp[V_SUM_MAX + 1][N_MAX];
bool v[V_SUM_MAX + 1][N_MAX];
 
// Function to solve the recurrence relation
int solveDp(int r, int i, vector<int>& w, vector<int>& val, int n)
{
    // Base cases
    if (r <= 0)
        return 0;
    if (i == n)
        return W_MAX;
    if (v[r][i])
        return dp[r][i];
 
    // Marking state as solved
    v[r][i] = 1;
 
    // Recurrence relation
    dp[r][i]
        = min(solveDp(r, i + 1, w, val, n),
              w[i] + solveDp(r - val[i],
                             i + 1, w, val, n));
    return dp[r][i];
}
 
// Function to return the maximum weight
int maxWeight(vector<int>& w, vector<int>& val, int n, int c)
{
 
    // Iterating through all possible values
    // to find the largest value that can
    // be represented by the given weights
    for (int i = V_SUM_MAX; i >= 0; i--) {
        if (solveDp(i, 0, w, val, n) <= c) {
            return i;
        }
    }
    return 0;
}
 
// Driver code
int main()
{
    vector<int> w = { 3, 4, 5 };
    vector<int> val = { 30, 50, 60 };
    int n = (int)w.size();
    int C = 8;
 
    cout << maxWeight(w, val, n, C);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
    static final int V_SUM_MAX = 1000;
    static final int N_MAX = 100;
    static final int W_MAX = 10000000;
     
    // To store the states of DP
    static int dp[][] = new int[V_SUM_MAX + 1][N_MAX];
    static boolean v[][] = new boolean [V_SUM_MAX + 1][N_MAX];
     
    // Function to solve the recurrence relation
    static int solveDp(int r, int i, int w[],      
                          int val[], int n)
    {
        // Base cases
        if (r <= 0)
            return 0;
             
        if (i == n)
            return W_MAX;
             
        if (v[r][i])
            return dp[r][i];
     
        // Marking state as solved
        v[r][i] = true;
     
        // Recurrence relation
        dp[r][i] = Math.min(solveDp(r, i + 1, w, val, n),
                     w[i] + solveDp(r - val[i],
                                    i + 1, w, val, n));
         
        return dp[r][i];
    }
     
    // Function to return the maximum weight
    static int maxWeight(int w[], int val[],
                         int n, int c)
    {
     
        // Iterating through all possible values
        // to find the largest value that can
        // be represented by the given weights
        for (int i = V_SUM_MAX; i >= 0; i--)
        {
            if (solveDp(i, 0, w, val, n) <= c)
            {
                return i;
            }
        }
        return 0;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int w[] = { 3, 4, 5 };
        int val[] = { 30, 50, 60 };
        int n = w.length;
        int C = 8;
     
        System.out.println(maxWeight(w, val, n, C));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
V_SUM_MAX = 1000
N_MAX = 100
W_MAX = 10000000
 
# To store the states of DP
dp = [[ 0 for i in range(N_MAX)]
          for i in range(V_SUM_MAX + 1)]
v = [[ 0 for i in range(N_MAX)]
         for i in range(V_SUM_MAX + 1)]
 
# Function to solve the recurrence relation
def solveDp(r, i, w, val, n):
     
    # Base cases
    if (r <= 0):
        return 0
    if (i == n):
        return W_MAX
    if (v[r][i]):
        return dp[r][i]
 
    # Marking state as solved
    v[r][i] = 1
 
    # Recurrence relation
    dp[r][i] = min(solveDp(r, i + 1, w, val, n),
            w[i] + solveDp(r - val[i], i + 1,
                            w, val, n))
    return dp[r][i]
 
# Function to return the maximum weight
def maxWeight( w, val, n, c):
 
    # Iterating through all possible values
    # to find the largest value that can
    # be represented by the given weights
    for i in range(V_SUM_MAX, -1, -1):
        if (solveDp(i, 0, w, val, n) <= c):
            return i
 
    return 0
 
# Driver code
if __name__ == '__main__':
    w = [3, 4, 5]
    val = [30, 50, 60]
    n = len(w)
    C = 8
 
    print(maxWeight(w, val, n, C))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
 
class GFG
{
    static readonly int V_SUM_MAX = 1000;
    static readonly int N_MAX = 100;
    static readonly int W_MAX = 10000000;
     
    // To store the states of DP
    static int [,]dp = new int[V_SUM_MAX + 1, N_MAX];
    static bool [,]v = new bool [V_SUM_MAX + 1, N_MAX];
     
    // Function to solve the recurrence relation
    static int solveDp(int r, int i, int []w,    
                       int []val, int n)
    {
        // Base cases
        if (r <= 0)
            return 0;
             
        if (i == n)
            return W_MAX;
             
        if (v[r, i])
            return dp[r, i];
     
        // Marking state as solved
        v[r, i] = true;
     
        // Recurrence relation
        dp[r, i] = Math.Min(solveDp(r, i + 1, w, val, n),
                     w[i] + solveDp(r - val[i],
                                    i + 1, w, val, n));
         
        return dp[r, i];
    }
     
    // Function to return the maximum weight
    static int maxWeight(int []w, int []val,
                         int n, int c)
    {
     
        // Iterating through all possible values
        // to find the largest value that can
        // be represented by the given weights
        for (int i = V_SUM_MAX; i >= 0; i--)
        {
            if (solveDp(i, 0, w, val, n) <= c)
            {
                return i;
            }
        }
        return 0;
    }
     
    // Driver code
    public static void Main(String[] args)
    {
        int []w = { 3, 4, 5 };
        int []val = { 30, 50, 60 };
        int n = w.Length;
        int C = 8;
     
        Console.WriteLine(maxWeight(w, val, n, C));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
var V_SUM_MAX = 1000
var N_MAX = 100
var W_MAX = 10000000
 
// To store the states of DP
var dp = Array.from(Array(V_SUM_MAX+1), ()=> Array(N_MAX));
var v = Array.from(Array(V_SUM_MAX+1), ()=> Array(N_MAX));
 
// Function to solve the recurrence relation
function solveDp(r, i, w, val, n)
{
    // Base cases
    if (r <= 0)
        return 0;
    if (i == n)
        return W_MAX;
    if (v[r][i])
        return dp[r][i];
 
    // Marking state as solved
    v[r][i] = 1;
 
    // Recurrence relation
    dp[r][i]
        = Math.min(solveDp(r, i + 1, w, val, n),
              w[i] + solveDp(r - val[i],
                             i + 1, w, val, n));
    return dp[r][i];
}
 
// Function to return the maximum weight
function maxWeight(w, val, n, c)
{
 
    // Iterating through all possible values
    // to find the largest value that can
    // be represented by the given weights
    for (var i = V_SUM_MAX; i >= 0; i--) {
        if (solveDp(i, 0, w, val, n) <= c) {
            return i;
        }
    }
    return 0;
}
 
// Driver code
var w = [3, 4, 5];
var val = [30, 50, 60];
var n = w.length;
var C = 8;
document.write( maxWeight(w, val, n, C));
 
</script>

90

Complejidad de tiempo: O(V_sum * N) donde V_sum es la suma de todos los valores en la array val[].

Espacio auxiliar: O(V_sum * N) donde V_sum es la suma de todos los valores en la array val[].