Dados N elementos, cada uno de los cuales tiene un peso C i dado y un valor de beneficio P i , la tarea es maximizar el beneficio seleccionando un máximo de K elementos que sumen un peso máximo W .
Ejemplos:
Entrada: N = 5, P[] = {2, 7, 1, 5, 3}, C[] = {2, 5, 2, 3, 4}, W = 8, K = 2.
Salida: 12
Explicación :
Aquí, la máxima ganancia posible es cuando tomamos 2 artículos: artículo2 (P[1] = 7 y C[1] = 5) y artículo4 (P[3] = 5 y C[3] = 3).
Por lo tanto, beneficio máximo = 7 + 5 = 12
Entrada: N = 5, P[] = {2, 7, 1, 5, 3}, C[] = {2, 5, 2, 3, 4}, W = 1, K = 2
Salida: 0
Explicación: Todos los pesos son mayores que 1. Por lo tanto, no se puede seleccionar ningún artículo.
Enfoque: Se prefiere el enfoque de programación dinámica al enfoque recursivo general. Primero verifiquemos que las condiciones de DP todavía se cumplen.
- Subproblemas superpuestos: cuando se intenta la solución recursiva, primero se agrega 1 elemento y el conjunto de soluciones es (1), (2), …(n). En la segunda iteración tenemos (1, 2) y así sucesivamente donde se recalculan (1) y (2). Por lo tanto, habrá soluciones superpuestas.
- Subestructura óptima: en general, cada elemento tiene solo dos opciones, puede incluirse en la solución o negarse. Para un subconjunto particular de z elementos, la solución para (z+1) th elemento puede tener una solución correspondiente a los z elementos o se puede agregar el (z+1) th elemento si no excede las restricciones de la mochila. De cualquier manera, se satisface la propiedad de subestructura óptima.
Derivemos la recurrencia. Consideremos una tabla tridimensional dp[N][W][K] , donde N es el número de elementos, W es la capacidad máxima de peso y K es el número máximo de artículos permitidos en la mochila. Definamos un estado dp[i][j][k] donde i denota que estamos considerando el i -ésimo elemento, j denota el peso actual llenado y k denota el número de elementos llenados hasta ahora.
Para cada estado dp[i][j][k], el beneficio es el del estado anterior (cuando no se incluye el estado actual) o el beneficio del elemento actual sumado al del estado anterior (cuando se selecciona el elemento actual). Por lo tanto, la relación de recurrencia es:
dp[i][j][k] = max( dp[i-1][j][k], dp[i-1][jW[i-1]][k-1] + P[i] )
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the extended
// Knapsack Approach
#include <bits/stdc++.h>
using namespace std;
// To store the dp values
vector<vector<vector<int> > > dp;
int maxProfit(int profit[], int weight[], int n, int max_W,
int max_E)
{
// for each element given
for (int i = 1; i <= n; i++) {
// For each possible
// weight value
for (int j = 1; j <= max_W; j++) {
// For each case where
// the total elements are
// less than the constraint
for (int k = 1; k <= max_E; k++) {
// To ensure that we dont
// go out of the array
if (j >= weight[i - 1]) {
dp[i][j][k] = max(
dp[i - 1][j][k],
dp[i - 1][j - weight[i - 1]][k - 1]
+ profit[i - 1]);
}
else {
dp[i][j][k] = dp[i - 1][j][k];
}
}
}
}
return dp[n][max_W][max_E];
}
// Driver Code
int main()
{
int n = 5;
int profit[] = { 2, 7, 1, 5, 3 };
int weight[] = { 2, 5, 2, 3, 4 };
int max_weight = 8;
int max_element = 2;
dp = vector<vector<vector<int> > >(
n + 1, vector<vector<int> >(
max_weight + 1,
vector<int>(max_element + 1, 0)));
cout << maxProfit(profit, weight, n, max_weight,
max_element)
<< "\n";
return 0;
}
Java
// Java code for the extended
// Knapsack Approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
// To store the dp values
static int[][][] dp = new int[100][100][100];
static int maxProfit(int profit[],
int weight[],
int n, int max_W,
int max_E)
{
// for each element given
for(int i = 1; i <= n; i++)
{
// For each possible
// weight value
for(int j = 1; j <= max_W; j++)
{
// For each case where
// the total elements are
// less than the constraint
for(int k = 1; k <= max_E; k++)
{
// To ensure that we dont
// go out of the array
if (j >= weight[i - 1])
{
dp[i][j][k] = Math.max(dp[i - 1][j][k],
dp[i - 1][j -
weight[i - 1]][k - 1] +
profit[i - 1]);
}
else
{
dp[i][j][k] = dp[i - 1][j][k];
}
}
}
}
return dp[n][max_W][max_E];
}
// Driver code
public static void main(String[] args)
{
int n = 5;
int profit[] = { 2, 7, 1, 5, 3 };
int weight[] = { 2, 5, 2, 3, 4 };
int max_weight = 8;
int max_element = 2;
System.out.println(maxProfit(profit,
weight, n,
max_weight,
max_element));
}
}
// This code is contributed by offbeat
Python3
# Python3 code for the extended # Knapsack Approach # To store the dp values dp=[] def maxProfit(profit, weight, n, max_W, max_E): # for each element given for i in range(1,n+1) : # For each possible # weight value for j in range(1,max_W+1) : # For each case where # the total elements are # less than the constra for k in range(1, max_E+1) : # To ensure that we dont # go out of the array if (j >= weight[i - 1]) : dp[i][j][k] = max( dp[i - 1][j][k], dp[i - 1][j - weight[i - 1]][k - 1] + profit[i - 1]) else : dp[i][j][k] = dp[i - 1][j][k] return dp[n][max_W][max_E] # Driver Code if __name__ == '__main__': n = 5 profit = [2, 7, 1, 5, 3 ] weight = [ 2, 5, 2, 3, 4 ] max_weight = 8 max_element = 2 dp = [[[0 for j in range(max_element + 1)]for i in range(max_weight + 1)] for k in range(n+1)] print(maxProfit(profit, weight, n, max_weight, max_element))
C#
// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// To store the dp values
static int[][][] dp = new int[100][][];
static int maxProfit(int[] profit, int[] weight,
int n, int max_W, int max_E)
{
// for each element given
for(int i = 1 ; i <= n ; i++)
{
// For each possible
// weight value
for(int j = 1 ; j <= max_W ; j++)
{
// For each case where
// the total elements are
// less than the constraint
for(int k = 1 ; k <= max_E ; k++)
{
// To ensure that we dont
// go out of the array
if (j >= weight[i - 1])
{
dp[i][j][k] = Math.Max(dp[i - 1][j][k],
dp[i - 1][j - weight[i - 1]][k - 1] + profit[i - 1]);
}
else
{
dp[i][j][k] = dp[i - 1][j][k];
}
}
}
}
return dp[n][max_W][max_E];
}
// Driver code
public static void Main(string[] args){
int n = 5;
int[] profit = new int[]{ 2, 7, 1, 5, 3 };
int[] weight = new int[]{ 2, 5, 2, 3, 4 };
int max_weight = 8;
int max_element = 2;
// Initialize dp
for(int i = 0 ; i < 100 ; i++){
dp[i] = new int[100][];
for(int j = 0 ; j < 100 ; j++){
dp[i][j] = new int[100];
}
}
Console.WriteLine(maxProfit(profit, weight, n,
max_weight, max_element));
}
}
// This code is contributed by subhamgoyal2014.
Javascript
<script>
// Javascript code for the extended
// Knapsack Approach
// To store the dp values
var dp = Array.from(Array(100), ()=>Array(100));
for(var i =0; i<100; i++)
for(var j =0; j<100; j++)
dp[i][j] = new Array(100).fill(0);
function maxProfit(profit,weight, n, max_W, max_E)
{
// for each element given
for (var i = 1; i <= n; i++)
{
// For each possible
// weight value
for (var j = 1; j <= max_W; j++)
{
// For each case where
// the total elements are
// less than the constraint
for (var k = 1; k <= max_E; k++)
{
// To ensure that we dont
// go out of the array
if (j >= weight[i-1])
{
dp[i][j][k]
= Math.max(dp[i - 1][j][k],
dp[i - 1][j -
weight[i-1]][k - 1]+
profit[i-1]);
}
else
{
dp[i][j][k]
= dp[i - 1][j][k];
}
}
}
}
return dp[n][max_W][max_E];
}
// Driver Code
var n = 5;
var profit = [2, 7, 1, 5, 3 ];
var weight = [2, 5, 2, 3, 4 ];
var max_weight = 8;
var max_element = 2;
document.write( maxProfit(profit,
weight, n,
max_weight,
max_element)
+ "<br>");
</script>
12
Complejidad de Tiempo: O(N * W * K)
Espacio Auxiliar: O(N * W * K)
Publicación traducida automáticamente
Artículo escrito por rushilshah y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA