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 codeint 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 codepublic 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 codeW = [ 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 codelet 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
17
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 codeint 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 codepublic 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 codeif __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
17
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.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
