Maximize cost of segment having weight at most K from given weight and cost of N items

0 0 10 minutes read

Given two arrays W[] and C[] containing weight and cost of N (1 to N) items respectively, and an integer K, find a segment from 1 to N, such that the total weight of the segment is at most K and the total cost is maximum. Print the cost of this segment.

Examples:

Input: N = 6, K = 20, W[] = {9, 7, 6, 5, 8, 4}, C[] = {7, 1, 3, 6, 8, 3}
Output: 17
Explanation: Pick the segment having index (2, 3, 4) Weight of segment {6, 5, 8} is 19. Cost of segment = 3 + 6 + 8 = 17 which is maximum possible.

Input: N = 3, K = 55, W[] = {10, 20, 30}, C[] = {60, 100, 120}
Output: 220

Naive Approach: The approach is to find all the segments whose weight is at most k and keep track of the maximum cost. For each element find a segment starting from this element.

Below is the implementation of the above approach.

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>

Output

Time Complexity: O(N*N), as we are using nested loops to traverse N*N times.

Auxiliary Space: O(1), as we are not using any extra space.

Efficient Approach: An efficient approach is to use the sliding window technique.

Let l and r denote the index of the first and last element in the current window respectively.
Start traversing the array and keep track of total weight and total cost of elements in the current window and the maximum total cost found till now.
While weight of window is greater than k, keep removing elements from the start of window.
Now update the maximum cost.
After traversing all the items return the maximum cost.

Below is the implementation of the above approach.

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>

Output

Time Complexity: O(N), as we are using a loop to traverse N times.

Auxiliary Space: O(1), as we are not using any extra space.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!