Dadas dos arrays W[] y C[] que contienen peso y costo de N (1 a N) artículos respectivamente, y un número entero K, encuentre un segmento de 1 a N, tal que el peso total del segmento sea como máximo K y el costo total es máximo. Imprime el costo de este segmento.
Ejemplos:
Entrada: N = 6, K = 20, W[] = {9, 7, 6, 5, 8, 4}, C[] = {7, 1, 3, 6, 8, 3}
Salida: 17
Explicación: Elija el segmento que tiene el índice (2, 3, 4) El peso del segmento {6, 5, 8} es 19. El costo del segmento = 3 + 6 + 8 = 17, que es el máximo posible.Entrada: N = 3, K = 55, W[] = {10, 20, 30}, C[] = {60, 100, 120}
Salida: 220
Enfoque ingenuo: el enfoque consiste en encontrar todos los segmentos cuyo peso sea como máximo k y realizar un seguimiento del costo máximo. Para cada elemento, busque un segmento a partir de este elemento.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to find maximum cost of
// a segment whose weight is at most K.
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum cost of
// a segment whose weight is at most k.
int findMaxCost(int W[], int C[],
int N, int K)
{
// Variable to keep track of
// current weight.
int weight = 0;
// Variable to keep track
// of current cost.
int cost = 0;
// variable to keep track of
// maximum cost of a segment
// whose weight is at most K.
int maxCost = 0;
// Loop to get segment
// having weight at most K
for (int l = 0; l < N; l++) {
weight = 0;
cost = 0;
for (int r = l; r < N; r++) {
weight += W[r];
cost += C[r];
if (weight <= K)
maxCost = max(maxCost, cost);
}
}
return maxCost;
}
// Driver code
int main()
{
int W[] = { 9, 7, 6, 5, 8, 4 };
int C[] = { 7, 1, 3, 6, 8, 3 };
int N = sizeof(W) / sizeof(W[0]);
int K = 20;
cout << findMaxCost(W, C, N, K);
return 0;
}
Java
// Java code to find maximum cost of
// a segment whose weight is at most K.
class GFG{
// Function to find the maximum cost of
// a segment whose weight is at most k.
static int findMaxCost(int W[], int C[],
int N, int K)
{
// Variable to keep track of
// current weight.
int weight = 0;
// Variable to keep track
// of current cost.
int cost = 0;
// variable to keep track of
// maximum cost of a segment
// whose weight is at most K.
int maxCost = 0;
// Loop to get segment
// having weight at most K
for (int l = 0; l < N; l++) {
weight = 0;
cost = 0;
for (int r = l; r < N; r++) {
weight += W[r];
cost += C[r];
if (weight <= K)
maxCost = Math.max(maxCost, cost);
}
}
return maxCost;
}
// Driver code
public static void main(String[] args)
{
int W[] = { 9, 7, 6, 5, 8, 4 };
int C[] = { 7, 1, 3, 6, 8, 3 };
int N = W.length;
int K = 20;
System.out.print(findMaxCost(W, C, N, K));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python code to find maximum cost of # a segment whose weight is at most K. # Function to find the maximum cost of # a segment whose weight is at most k. def findMaxCost(W, C, N, K) : # Variable to keep track of # current weight. weight = 0; # Variable to keep track # of current cost. cost = 0; # variable to keep track of # maximum cost of a segment # whose weight is at most K. maxCost = 0; # Loop to get segment # having weight at most K for l in range(N): weight = 0; cost = 0; for r in range(l, N): weight += W[r]; cost += C[r]; if (weight <= K): maxCost = max(maxCost, cost); return maxCost; # Driver code W = [ 9, 7, 6, 5, 8, 4 ]; C = [ 7, 1, 3, 6, 8, 3 ]; N = len(W); K = 20; print(findMaxCost(W, C, N, K)); # This code is contributed by Saurabh Jaiswal
C#
// C# code to find maximum cost of
// a segment whose weight is at most K.
using System;
class GFG
{
// Function to find the maximum cost of
// a segment whose weight is at most k.
static int findMaxCost(int[] W, int[] C, int N, int K)
{
// Variable to keep track of
// current weight.
int weight = 0;
// Variable to keep track
// of current cost.
int cost = 0;
// variable to keep track of
// maximum cost of a segment
// whose weight is at most K.
int maxCost = 0;
// Loop to get segment
// having weight at most K
for (int l = 0; l < N; l++) {
weight = 0;
cost = 0;
for (int r = l; r < N; r++) {
weight += W[r];
cost += C[r];
if (weight <= K)
maxCost = Math.Max(maxCost, cost);
}
}
return maxCost;
}
// Driver code
public static void Main()
{
int[] W = { 9, 7, 6, 5, 8, 4 };
int[] C = { 7, 1, 3, 6, 8, 3 };
int N = W.Length;
int K = 20;
Console.WriteLine(findMaxCost(W, C, N, K));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code to find maximum cost of
// a segment whose weight is at most K.
// Function to find the maximum cost of
// a segment whose weight is at most k.
function findMaxCost(W, C, N, K)
{
// Variable to keep track of
// current weight.
let weight = 0;
// Variable to keep track
// of current cost.
let cost = 0;
// variable to keep track of
// maximum cost of a segment
// whose weight is at most K.
let maxCost = 0;
// Loop to get segment
// having weight at most K
for(let l = 0; l < N; l++)
{
weight = 0;
cost = 0;
for(let r = l; r < N; r++)
{
weight += W[r];
cost += C[r];
if (weight <= K)
maxCost = Math.max(maxCost, cost);
}
}
return maxCost;
}
// Driver code
let W = [ 9, 7, 6, 5, 8, 4 ];
let C = [ 7, 1, 3, 6, 8, 3 ];
let N = W.length;
let K = 20;
document.write(findMaxCost(W, C, N, K));
// This code is contributed by Potta Lokesh
</script>
Producción
17
Complejidad de tiempo : O (N * N), ya que estamos usando bucles anidados para atravesar N * N veces.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.
Enfoque eficiente: un enfoque eficiente es utilizar la técnica de la ventana deslizante.
- Deje que l y r denoten el índice del primer y último elemento en la ventana actual, respectivamente.
- Comience a recorrer la array y realice un seguimiento del peso total y el costo total de los elementos en la ventana actual y el costo total máximo encontrado hasta ahora.
- Si bien el peso de la ventana es mayor que k, siga eliminando elementos desde el inicio de la ventana.
- Ahora actualice el costo máximo.
- Después de recorrer todos los elementos, devuelva el costo máximo.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to find maximum cost of
// a segment whose weight is at most K.
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum cost of
// a segment whose weight is at most K.
int findMaxCost(int W[], int C[],
int N, int K)
{
// Variable to keep track
// of current weight.
int weight = 0;
// Variable to keep track
// of current cost.
int cost = 0;
// Variable to keep track of
// maximum cost of a segment
// whose weight is at most K.
int maxCost = 0;
// Loop to implement
// sliding window technique
int l = 0;
for (int r = 0; r < N; r++) {
// Add current element to the window.
weight += W[r];
cost += C[r];
// Keep removing elements
// from the start of current window
// while weight is greater than K
while(weight > K)
{
weight -= W[l];
cost -= C[l];
l++;
}
// Update maxCost
maxCost = max(maxCost, cost);
}
return maxCost;
}
// Driver code
int main()
{
int W[] = {9, 7, 6, 5, 8, 4};
int C[] = {7, 1, 3, 6, 8, 3};
int N = sizeof(W) / sizeof(W[0]);
int K = 20;
cout << findMaxCost(W, C, N, K);
return 0;
}
Java
// Java code to find maximum cost of
// a segment whose weight is at most K.
class GFG{
// Function to find the maximum cost of
// a segment whose weight is at most K.
static int findMaxCost(int W[], int C[],
int N, int K)
{
// Variable to keep track
// of current weight.
int weight = 0;
// Variable to keep track
// of current cost.
int cost = 0;
// Variable to keep track of
// maximum cost of a segment
// whose weight is at most K.
int maxCost = 0;
// Loop to implement
// sliding window technique
int l = 0;
for (int r = 0; r < N; r++) {
// Add current element to the window.
weight += W[r];
cost += C[r];
// Keep removing elements
// from the start of current window
// while weight is greater than K
while(weight > K)
{
weight -= W[l];
cost -= C[l];
l++;
}
// Update maxCost
maxCost = Math.max(maxCost, cost);
}
return maxCost;
}
// Driver code
public static void main(String[] args)
{
int W[] = {9, 7, 6, 5, 8, 4};
int C[] = {7, 1, 3, 6, 8, 3};
int N = W.length;
int K = 20;
System.out.print(findMaxCost(W, C, N, K));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 code to find maximum cost of # a segment whose weight is at most K. # Function to find the maximum cost of # a segment whose weight is at most K. def findMaxCost(W, C, N, K): # Variable to keep track # of current weight. weight = 0 # Variable to keep track # of current cost. cost = 0 # Variable to keep track of # maximum cost of a segment # whose weight is at most K. maxCost = 0 # Loop to implement # sliding window technique l = 0 for r in range(N): # Add current element to the window. weight += W[r] cost += C[r] # Keep removing elements # from the start of current window # while weight is greater than K while(weight > K): weight -= W[l] cost -= C[l] l += 1 # Update maxCost maxCost = max(maxCost, cost) return maxCost # Driver code if __name__ == "__main__": W = [9, 7, 6, 5, 8, 4] C = [7, 1, 3, 6, 8, 3] N = len(W) K = 20 print(findMaxCost(W, C, N, K)) # This code is contributed by gaurav01.
C#
// C# code to find maximum cost of
// a segment whose weight is at most K.
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the maximum cost of
// a segment whose weight is at most K.
static int findMaxCost(int []W, int []C,
int N, int K)
{
// Variable to keep track
// of current weight.
int weight = 0;
// Variable to keep track
// of current cost.
int cost = 0;
// Variable to keep track of
// maximum cost of a segment
// whose weight is at most K.
int maxCost = 0;
// Loop to implement
// sliding window technique
int l = 0;
for (int r = 0; r < N; r++) {
// Add current element to the window.
weight += W[r];
cost += C[r];
// Keep removing elements
// from the start of current window
// while weight is greater than K
while(weight > K)
{
weight -= W[l];
cost -= C[l];
l++;
}
// Update maxCost
maxCost = Math.Max(maxCost, cost);
}
return maxCost;
}
// Driver code
public static void Main(String[] args)
{
int []W = {9, 7, 6, 5, 8, 4};
int []C = {7, 1, 3, 6, 8, 3};
int N = W.Length;
int K = 20;
Console.Write(findMaxCost(W, C, N, K));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code to find maximum cost of
// a segment whose weight is at most K.
// Function to find the maximum cost of
// a segment whose weight is at most K.
const findMaxCost = (W, C, N, K) => {
// Variable to keep track
// of current weight.
let weight = 0;
// Variable to keep track
// of current cost.
let cost = 0;
// Variable to keep track of
// maximum cost of a segment
// whose weight is at most K.
let maxCost = 0;
// Loop to implement
// sliding window technique
let l = 0;
for (let r = 0; r < N; r++) {
// Add current element to the window.
weight += W[r];
cost += C[r];
// Keep removing elements
// from the start of current window
// while weight is greater than K
while (weight > K) {
weight -= W[l];
cost -= C[l];
l++;
}
// Update maxCost
maxCost = Math.max(maxCost, cost);
}
return maxCost;
}
// Driver code
let W = [9, 7, 6, 5, 8, 4];
let C = [7, 1, 3, 6, 8, 3];
let N = W.length;
let K = 20;
document.write(findMaxCost(W, C, N, K));
// This code is contributed by rakesh sahani.
</script>
Producción
17
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por nikhilkumarmishra120 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA