Mochila Doble | Programación dinámica

Dada una array ‘arr’ que contiene el peso de ‘N’ artículos distintos y dos mochilas que pueden soportar pesos ‘W1’ y ‘W2’, la tarea es encontrar la suma del subconjunto más grande de la array ‘arr’, que cabe en las dos mochilas. No está permitido romper ningún artículo en dos, es decir, un artículo debe colocarse en una de las bolsas como un todo.
Ejemplos: 
 

Entrada: arr[] = {8, 3, 2} 
W1 = 10, W2 = 3 
Salida: 13 
El primer y tercer objeto van en la primera mochila. El segundo objeto va en la segunda mochila. Por lo tanto, el peso total se convierte en 13.
Entrada: arr[] = {8, 5, 3} 
W1 = 10, W2 = 3 
Salida: 11 
 

Solución: 
Una solución recursiva es probar todas las formas posibles de llenar las dos mochilas y elegir la que da el peso máximo. 
Para optimizar la idea anterior, necesitamos determinar los estados de DP, sobre los que construiremos nuestra solución. Después de un poco de observación, podemos determinar que esto se puede representar en tres estados (i, w1_r, w2_r) . Aquí ‘i’ significa el índice del elemento que estamos tratando de almacenar, w1_r significa el espacio restante de la primera mochila y w2_r significa el espacio restante de la segunda mochila. Por lo tanto, el problema se puede resolver utilizando una programación dinámica tridimensional con una relación de recurrencia 
 

DP[i][w1_r][w2_r] = max( DP[i + 1][w1_r][w2_r],
                    arr[i] + DP[i + 1][w1_r - arr[i]][w2_r],
                    arr[i] + DP[i + 1][w1_r][w2_r - arr[i]])

La explicación de la relación de recurrencia anterior es la siguiente: 
 

Para cada ‘i’, podemos: 
 

1. No seleccione el elemento ‘i’.
2. Llene el artículo ‘i’ en la primera mochila.
3. Rellena el artículo ‘i’ en la segunda mochila.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
#define maxN 31
#define maxW 31
using namespace std;
 
// 3D array to store
// states of DP
int dp[maxN][maxW][maxW];
 
// w1_r represents remaining capacity of 1st knapsack
// w2_r represents remaining capacity of 2nd knapsack
// i represents index of the array arr we are working on
int maxWeight(int* arr, int n, int w1_r, int w2_r, int i)
{
    // Base case
    if (i == n)
        return 0;
    if (dp[i][w1_r][w2_r] != -1)
        return dp[i][w1_r][w2_r];
 
    // Variables to store the result of three
    // parts of recurrence relation
    int fill_w1 = 0, fill_w2 = 0, fill_none = 0;
 
    if (w1_r >= arr[i])
        fill_w1 = arr[i] +
         maxWeight(arr, n, w1_r - arr[i], w2_r, i + 1);
 
    if (w2_r >= arr[i])
        fill_w2 = arr[i] +
         maxWeight(arr, n, w1_r, w2_r - arr[i], i + 1);
 
    fill_none = maxWeight(arr, n, w1_r, w2_r, i + 1);
 
    // Store the state in the 3D array
    dp[i][w1_r][w2_r] = max(fill_none, max(fill_w1, fill_w2));
 
    return dp[i][w1_r][w2_r];
}
 
// Driver code
int main()
{
    // Input array
    int arr[] = { 8, 2, 3 };
 
    // Initializing the array with -1
    memset(dp, -1, sizeof(dp));
 
    // Number of elements in the array
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Capacity of knapsacks
    int w1 = 10, w2 = 3;
 
    // Function to be called
    cout << maxWeight(arr, n, w1, w2, 0);
    return 0;
}

// Java implementation of the above approach
 
class GFG
{
    static int maxN = 31;
    static int maxW = 31;
 
    // 3D array to store
    // states of DP
    static int dp [][][] = new int[maxN][maxW][maxW];
     
    // w1_r represents remaining capacity of 1st knapsack
    // w2_r represents remaining capacity of 2nd knapsack
    // i represents index of the array arr we are working on
    static int maxWeight(int arr [] , int n, int w1_r, int w2_r, int i)
    {
        // Base case
        if (i == n)
            return 0;
        if (dp[i][w1_r][w2_r] != -1)
            return dp[i][w1_r][w2_r];
     
        // Variables to store the result of three
        // parts of recurrence relation
        int fill_w1 = 0, fill_w2 = 0, fill_none = 0;
     
        if (w1_r >= arr[i])
            fill_w1 = arr[i] +
            maxWeight(arr, n, w1_r - arr[i], w2_r, i + 1);
     
        if (w2_r >= arr[i])
            fill_w2 = arr[i] +
            maxWeight(arr, n, w1_r, w2_r - arr[i], i + 1);
     
        fill_none = maxWeight(arr, n, w1_r, w2_r, i + 1);
     
        // Store the state in the 3D array
        dp[i][w1_r][w2_r] = Math.max(fill_none, Math.max(fill_w1, fill_w2));
     
        return dp[i][w1_r][w2_r];
    }
     
    // Driver code
    public static void main (String[] args)
    {
     
        // Input array
        int arr[] = { 8, 2, 3 };
     
        // Initializing the array with -1
         
        for (int i = 0; i < maxN ; i++)
            for (int j = 0; j < maxW ; j++)
                for (int k = 0; k < maxW ; k++)
                        dp[i][j][k] = -1;
         
        // Number of elements in the array
        int n = arr.length;
     
        // Capacity of knapsacks
        int w1 = 10, w2 = 3;
     
        // Function to be called
        System.out.println(maxWeight(arr, n, w1, w2, 0));
    }
}
 
// This code is contributed by ihritik

# Python3 implementation of the above approach
 
# w1_r represents remaining capacity of 1st knapsack
# w2_r represents remaining capacity of 2nd knapsack
# i represents index of the array arr we are working on
def maxWeight(arr, n, w1_r, w2_r, i):
 
    # Base case
    if i == n:
        return 0
    if dp[i][w1_r][w2_r] != -1:
        return dp[i][w1_r][w2_r]
 
    # Variables to store the result of three
    # parts of recurrence relation
    fill_w1, fill_w2, fill_none = 0, 0, 0
 
    if w1_r >= arr[i]:
        fill_w1 = arr[i] + maxWeight(arr, n, w1_r - arr[i],
                                             w2_r, i + 1)
 
    if w2_r >= arr[i]:
        fill_w2 = arr[i] + maxWeight(arr, n, w1_r,
                                     w2_r - arr[i], i + 1)
 
    fill_none = maxWeight(arr, n, w1_r, w2_r, i + 1)
 
    # Store the state in the 3D array
    dp[i][w1_r][w2_r] = max(fill_none, max(fill_w1,
                                           fill_w2))
 
    return dp[i][w1_r][w2_r]
 
 
# Driver code
if __name__ == "__main__":
 
    # Input array
    arr = [8, 2, 3]
    maxN, maxW = 31, 31
     
    # 3D array to store
    # states of DP
    dp = [[[-1] * maxW] * maxW] * maxN
     
    # Number of elements in the array
    n = len(arr)
 
    # Capacity of knapsacks
    w1, w2 = 10, 3
 
    # Function to be called
    print(maxWeight(arr, n, w1, w2, 0))
     
# This code is contributed by Rituraj Jain

// C# implementation of the above approach
using System;
 
class GFG
{
    static int maxN = 31;
    static int maxW = 31;
 
    // 3D array to store
    // states of DP
    static int [ , , ] dp = new int[maxN, maxW, maxW];
     
    // w1_r represents remaining capacity of 1st knapsack
    // w2_r represents remaining capacity of 2nd knapsack
    // i represents index of the array arr we are working on
    static int maxWeight(int [] arr, int n, int w1_r,
                                    int w2_r, int i)
    {
        // Base case
        if (i == n)
            return 0;
        if (dp[i ,w1_r, w2_r] != -1)
            return dp[i, w1_r, w2_r];
     
        // Variables to store the result of three
        // parts of recurrence relation
        int fill_w1 = 0, fill_w2 = 0, fill_none = 0;
     
        if (w1_r >= arr[i])
            fill_w1 = arr[i] +
            maxWeight(arr, n, w1_r - arr[i], w2_r, i + 1);
     
        if (w2_r >= arr[i])
            fill_w2 = arr[i] +
            maxWeight(arr, n, w1_r, w2_r - arr[i], i + 1);
     
        fill_none = maxWeight(arr, n, w1_r, w2_r, i + 1);
     
        // Store the state in the 3D array
        dp[i, w1_r, w2_r] = Math.Max(fill_none, Math.Max(fill_w1, fill_w2));
     
        return dp[i, w1_r, w2_r];
    }
     
    // Driver code
    public static void Main ()
    {
     
        // Input array
        int [] arr = { 8, 2, 3 };
     
        // Initializing the array with -1
         
        for (int i = 0; i < maxN ; i++)
            for (int j = 0; j < maxW ; j++)
                for (int k = 0; k < maxW ; k++)
                        dp[i, j, k] = -1;
         
        // Number of elements in the array
        int n = arr.Length;
     
        // Capacity of knapsacks
        int w1 = 10, w2 = 3;
     
        // Function to be called
        Console.WriteLine(maxWeight(arr, n, w1, w2, 0));
    }
}
 
// This code is contributed by ihritik

<script>
 
// Javascript implementation of
// the above approach
 
var maxN = 31
var maxW = 31
 
// 3D array to store
// states of DP
var dp = Array(maxN);
 
for(var i=0;i<maxN;i++)
{
    dp[i] = Array(maxW);
    for(var j =0; j<maxW; j++)
    {
        dp[i][j] = Array(maxW).fill(-1);
    }
}
 
// w1_r represents remaining
// capacity of 1st knapsack
// w2_r represents remaining
// capacity of 2nd knapsack
// i represents index of the array arr
// we are working on
function maxWeight(arr, n, w1_r, w2_r, i)
{
    // Base case
    if (i == n)
        return 0;
    if (dp[i][w1_r][w2_r] != -1)
        return dp[i][w1_r][w2_r];
 
    // Variables to store the result of three
    // parts of recurrence relation
    var fill_w1 = 0, fill_w2 = 0, fill_none = 0;
 
    if (w1_r >= arr[i])
        fill_w1 = arr[i] +
         maxWeight(arr, n, w1_r - arr[i],
         w2_r, i + 1);
 
    if (w2_r >= arr[i])
        fill_w2 = arr[i] +
         maxWeight(arr, n, w1_r, w2_r -
         arr[i], i + 1);
 
    fill_none = maxWeight(arr, n, w1_r,
    w2_r, i + 1);
 
    // Store the state in the 3D array
    dp[i][w1_r][w2_r] = Math.max(fill_none,
    Math.max(fill_w1, fill_w2));
 
    return dp[i][w1_r][w2_r];
}
 
// Driver code
// Input array
var arr = [8, 2, 3 ];
 
// Number of elements in the array
var n = arr.length;
 
// Capacity of knapsacks
var w1 = 10, w2 = 3;
 
// Function to be called
document.write( maxWeight(arr, n, w1, w2, 0));
 
</script>

13

Complejidad de tiempo: O(N*W1*W2)
Espacio auxiliar: O(N*W1*W2))