Dada una array de enteros W[] que consiste en pesos de artículos y mochilas ‘K’ de capacidad ‘C’, encuentre el peso máximo que podemos poner en las mochilas si no se permite romper un artículo.
Ejemplos:
Entrada: w[] = {3, 9, 8}, k = 1, c = 11
Salida: 11
El subconjunto requerido será {3, 8}
donde 3+8 = 11Entrada: w[] = {3, 9, 8}, k = 1, c = 10
Salida: 9
Usaremos la programación dinámica para resolver este problema.
Usaremos dos variables para representar los estados de DP.
- ‘i’: el índice actual en el que estamos trabajando.
- ‘R’ – Contiene la capacidad restante de todas y cada una de las mochilas.
Ahora, ¿cómo almacenará una sola variable la capacidad restante de cada mochila?
Para eso, inicializaremos ‘R’ como R = C+ C*(C+1) + C*(C+1)^2 + C*(C+1)^3 ..+ C*(C+1 )^(k-1)
Esto inicializa todas las mochilas ‘k’ con capacidad ‘C’.
Ahora, necesitamos realizar dos consultas:
- Lectura del espacio restante de la j-ésima mochila: (r/(c+1)^(j-1))%(c+1).
- Disminución del espacio restante de la j-ésima mochila en x: establece r = r – x*(c+1)^(j-1).
Ahora, en cada paso, tendremos k+1 opciones.
- Índice de rechazo ‘i’.
- Ponga el artículo ‘i’ en la mochila 1.
- Ponga el artículo ‘i’ en la mochila 2.
- Ponga el artículo ‘i’ en la mochila 3.
Elegiremos el camino que maximice el resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// 2-d array to store states of DP
vector<vector<int> > dp;
// 2-d array to store if a state
// has been solved
vector<vector<bool> > v;
// Vector to store power of variable 'C'.
vector<int> exp_c;
// function to compute the states
int FindMax(int i, int r, int w[],
int n, int c, int k)
{
// Base case
if (i >= n)
return 0;
// Checking 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] = FindMax(i + 1, r, w, n, c, k);
// Recurrence relation
for (int j = 0; j < k; j++) {
int x = (r / exp_c[j]) % (c + 1);
if (x - w[i] >= 0)
dp[i][r] = max(dp[i][r], w[i] +
FindMax(i + 1, r - w[i] * exp_c[j], w, n, c, k));
}
// Returning the solved state
return dp[i][r];
}
// Function to initialize global variables
// and find the initial value of 'R'
int PreCompute(int n, int c, int k)
{
// Resizing the variables
exp_c.resize(k);
exp_c[0] = 1;
for (int i = 1; i < k; i++){
exp_c[i] = (exp_c[i - 1] * (c + 1));
}
dp.resize(n);
for (int i = 0; i < n; i++){
dp[i].resize(exp_c[k - 1] * (c + 1), 0);
}
v.resize(n);
for (int i = 0; i < n; i++){
v[i].resize(exp_c[k - 1] * (c + 1), 0);
}
// Variable to store the initial value of R
int R = 0;
for (int i = 0; i < k; i++){
R += exp_c[i] * c;
}
return R;
}
// Driver Code
int main()
{
// Input array
int w[] = { 3, 8, 9 };
// number of knapsacks and capacity
int k = 1, c = 11;
int n = sizeof(w) / sizeof(int);
// Performing required pre-computation
int r = PreCompute(n, c, k);
// finding the required answer
cout << FindMax(0, r, w, n, c, k);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG
{
// 2-d array to store if a state
// has been solved
static ArrayList<ArrayList<Boolean>> v =
new ArrayList<ArrayList<Boolean>>();
// 2-d array to store states of DP
static ArrayList<ArrayList<Integer>> dp =
new ArrayList<ArrayList<Integer>>();
// Vector to store power of variable 'C'.
static ArrayList<Integer> exp_c =
new ArrayList<Integer>();
// function to compute the states
static int FindMax(int i, int r, int w[],
int n, int c, int k)
{
// Base case
if (i >= n)
{
return 0;
}
// Checking if a state has been solved
if(v.get(i).get(r))
{
return dp.get(i).get(r);
}
// Setting a state as solved
v.get(i).set(r, true);
dp.get(i).set(r,FindMax(i + 1, r,
w, n, c, k));
// Recurrence relation
for (int j = 0; j < k; j++)
{
int x = (r / exp_c.get(j)) % (c + 1);
if (x - w[i] >= 0)
{
dp.get(i).set(r,Math.max(dp.get(i).get(r),w[i] +
FindMax(i + 1, r - w[i] *
exp_c.get(j), w, n, c, k)));
}
}
// Returning the solved state
return dp.get(i).get(r);
}
// Function to initialize global variables
// and find the initial value of 'R'
static int PreCompute(int n, int c, int k)
{
// Resizing the variables
for(int i = 0; i < k; i++)
{
exp_c.add(0);
}
exp_c.set(0, 1);
for (int i = 1; i < k; i++)
{
exp_c.set(i,(exp_c.get(i - 1) * (c + 1)));
}
for (int i = 0; i < n; i++)
{
dp.add(new ArrayList<Integer>());
}
for (int i = 0; i < n; i++)
{
for(int j = 0; j < (exp_c.get(k-1) * (c + 1)) ; j++ )
{
dp.get(i).add(0);
}
}
for (int i = 0; i < n; i++)
{
v.add(new ArrayList<Boolean>(Arrays.asList(
new Boolean[(exp_c.get(k-1) * (c + 1))])));
}
for (int i = 0; i < n; i++)
{
Collections.fill(v.get(i), Boolean.FALSE);
}
// Variable to store the initial value of R
int R = 0;
for(int i = 0; i < k; i++)
{
R += exp_c.get(i) * c;
}
return R;
}
// Driver Code
public static void main (String[] args)
{
// Input array
int w[] = { 3, 8, 9 };
// number of knapsacks and capacity
int k = 1, c = 11;
int n = w.length;
// Performing required pre-computation
int r = PreCompute(n, c, k);
// finding the required answer
System.out.println(FindMax(0, r, w, n, c, k));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# 2-d array to store states of DP x = 100 dp = [[0 for i in range(x)] for i in range(x)] # 2-d array to store if a state # has been solved v = [[0 for i in range(x)] for i in range(x)] # Vector to store power of variable 'C'. exp_c = [] # function to compute the states def FindMax(i, r, w, n, c, k): # Base case if (i >= n): return 0 # Checking 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] = FindMax(i + 1, r, w, n, c, k) # Recurrence relation for j in range(k): x = (r // exp_c[j]) % (c + 1) if (x - w[i] >= 0): dp[i][r] = max(dp[i][r], w[i] + FindMax(i + 1, r - w[i] * exp_c[j], w, n, c, k)) # Returning the solved state return dp[i][r] # Function to initialize global variables # and find the initial value of 'R' def PreCompute(n, c, k): # Resizing the variables exp_c.append(1) for i in range(1, k): exp_c[i] = (exp_c[i - 1] * (c + 1)) # Variable to store the initial value of R R = 0 for i in range(k): R += exp_c[i] * c return R # Driver Code # Input array w =[3, 8, 9] # number of knapsacks and capacity k = 1 c = 11 n = len(w) # Performing required pre-computation r = PreCompute(n, c, k) # finding the required answer print(FindMax(0, r, w, n, c, k)) # This code is contributed by Mohit Kumar
C#
using System;
using System.Collections.Generic;
class GFG{
// 2-d array to store if a state
// has been solved
static List<List<bool>> v = new List<List<bool>>();
// 2-d array to store states of DP
static List<List<int>> dp = new List<List<int>>();
// Vector to store power of variable 'C'.
static List<int> exp_c = new List<int>();
// Function to compute the states
static int FindMax(int i, int r, int[] w,
int n, int c, int k)
{
// Base case
if (i >= n)
{
return 0;
}
// Checking 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] = FindMax(i + 1, r, w, n, c, k);
// Recurrence relation
for(int j = 0; j < k; j++)
{
int x = (r / exp_c[j]) % (c + 1);
if (x - w[i] >= 0)
{
dp[i][r] = Math.Max(dp[i][r], w[i] +
FindMax(i + 1,
r - w[i] *
exp_c[j],
w, n, c, k));
}
}
// Returning the solved state
return dp[i][r];
}
// Function to initialize global variables
// and find the initial value of 'R'
static int PreCompute(int n, int c, int k)
{
// Resizing the variables
for(int i = 0; i < k; i++)
{
exp_c.Add(0);
}
exp_c[0] = 1;
for(int i = 1; i < k; i++)
{
exp_c[i] = (exp_c[i - 1] * (c + 1));
}
for(int i = 0; i < n; i++)
{
dp.Add(new List<int>());
}
for(int i = 0; i < n; i++)
{
for(int j = 0;
j < (exp_c[k - 1] * (c + 1));
j++ )
{
dp[i].Add(0);
}
}
for(int i = 0; i < n; i++)
{
v.Add(new List<bool>());
}
for(int i = 0; i < n; i++)
{
for(int j = 0;
j < (exp_c[k - 1] * (c + 1));
j++ )
{
v[i].Add(false);
}
}
// Variable to store the initial value of R
int R = 0;
for(int i = 0; i < k; i++)
{
R += exp_c[i] * c;
}
return R;
}
// Driver code
static public void Main()
{
// Input array
int[] w = { 3, 8, 9 };
// number of knapsacks and capacity
int k = 1, c = 11;
int n = w.Length;
// Performing required pre-computation
int r = PreCompute(n, c, k);
// finding the required answer
Console.WriteLine(FindMax(0, r, w, n, c, k));
}
}
// This code is contributed by rag2127
Javascript
<script>
// 2-d array to store if a state
// has been solved
let v =[];
// 2-d array to store states of DP
let dp =[];
// Vector to store power of variable 'C'.
let exp_c =[];
// function to compute the states
function FindMax(i,r,w,n,c,k)
{
// Base case
if (i >= n)
{
return 0;
}
// Checking 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] =FindMax(i + 1, r,
w, n, c, k);
// Recurrence relation
for (let j = 0; j < k; j++)
{
let x = (r / exp_c[j]) % (c + 1);
if (x - w[i] >= 0)
{
dp[i][r] = Math.max(dp[i][r],w[i] +
FindMax(i + 1, r - w[i] *
exp_c[j], w, n, c, k));
}
}
// Returning the solved state
return dp[i][r];
}
// Function to initialize global variables
// and find the initial value of 'R'
function PreCompute(n,c,k)
{
// Resizing the variables
for(let i = 0; i < k; i++)
{
exp_c.push(0);
}
exp_c[0]= 1;
for (let i = 1; i < k; i++)
{
exp_c[i]=(exp_c[i - 1] * (c + 1));
}
for (let i = 0; i < n; i++)
{
dp.push([]);
}
for (let i = 0; i < n; i++)
{
for(let j = 0; j < (exp_c[k-1] * (c + 1)) ; j++ )
{
dp[i][0];
}
}
for (let i = 0; i < n; i++)
{
v.push([(exp_c[k-1] * (c + 1))]);
}
for (let i = 0; i < n; i++)
{
for(let j=0;j<v[i].length;j++)
{
v[i][j]=false;
}
}
// Variable to store the initial value of R
let R = 0;
for(let i = 0; i < k; i++)
{
R += exp_c[i] * c;
}
return R;
}
// Driver Code
// Input array
let w=[3, 8, 9];
// number of knapsacks and capacity
let k = 1, c = 11;
let n = w.length;
// Performing required pre-computation
let r = PreCompute(n, c, k);
// finding the required answer
document.write(FindMax(0, r, w, n, c, k));
// This code is contributed by unknown2108
</script>
Producción:
11
Complejidad del tiempo: O(N*k*C^k).
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA