Questions tagged [greedy]
A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
1,019
questions
0
votes
0
answers
16
views
Greedy Algorithm problem: how to assign workers with different skillsets to jobs
I'm trying to write an algorithm to optimize my performance in the smartphone game Tiny Tower.
I have "n" workers.
There are 5 types of stores: store_types=['green', 'blue', 'yellow', '...
-1
votes
0
answers
27
views
Greedy Algorithm in Flutter/Dart [closed]
I am trying to implement the Greedy Algorithm in my Farming Application.
Basically the user enters the crop they want to grow and the surface. I want to be able to tell the user, based on his input, ...
1
vote
0
answers
32
views
Greedy approach correctness
I'm trying to practice some questions based on greedy algorithms and came across this question:
In organization ABC, the employees
have an underlying hierarchy, where the CEO is at the top and every ...
0
votes
1
answer
40
views
Questions for Algorithm pseudocode of greedy problem
I've been solving algorithm problems but couldn't solve this question.
It doesn't matter if it is any programming language, I would love to see your approach.
Problem:
Say there are two arrays A, B, ...
-2
votes
2
answers
42
views
A greedy + binary search programming problem
Problem Description:
Lian raises a pig and wants to sell it to the market. The pigs on the market need to have quality assurance, at least m kg. He has n bags of feed to feed the pigs, and the weight ...
1
vote
2
answers
89
views
CHEAPEST cost of intervals to cover the target interval
So I stumbled across this problem someone send in a Discord gc (irrelevant), and it seemed really intriguing.
We have a certain target interval (in this example, [20, 100]) and then some other ...
0
votes
1
answer
15
views
Find best combination of X reference items to fullfill maximum number of order
With this example
order_book = [ {"id": 1, "reference_items": ["item1", "item2", "item4"]}, {"id": 2, "reference_items": ["...
0
votes
1
answer
28
views
How to form a greedy argument in Dafny?
I am trying to verify the following solution to this problem.
https://leetcode.com/problems/diameter-of-binary-tree/description/
function diameter(node: TreeNode | null): [number, number] {
if(node =...
0
votes
1
answer
66
views
What is wrong with my CS50 cash week 1 problem?
This is Cs50 problem set1 cash. i don't get it, if you get the largest coins then for 73 shouldn't it be ( 2 qualters, 2dimes and 3 pennies) and for 28 shouldn't it be (1 qualter, and 3 pennies). can ...
0
votes
1
answer
39
views
How to classify elements in a linear array under constraints?
I face a problem that is more logical in nature, but at the end I have to design an algorithm to solve it, so that's why I post it here. Perhaps someone will provide a fresh perspective on the problem,...
0
votes
0
answers
33
views
Greedy algorithm, error : expected identifer
So I'm writing code for a class, and the job is to create a greedy algorithm. I wrote code that should work, but I'm getting an error code. Did I forget a {} somewhere or what's wrong here? The exact ...
-1
votes
1
answer
49
views
error in arraylist sorting using collections.sort() [closed]
I am writing a code on fractional knapsack. But, the sorting algorithm is not working well. And hence my code is not working correctly.
This is my code:
import java.util.*;
class Item {
int profit,...
-1
votes
2
answers
48
views
Sum of subsequences in cpp, I have to print all the sums of subsequences. I'm storing it in vector g here. result shows g is empty
class Solution
{
public:
void f(vector <int> arr, int N, int i , int sum, vector <int> g){
if (i>= N){// when index reaches the end of the array
g.push_back(sum);...
2
votes
1
answer
43
views
Efficient Algorithm for Amount allocation problem
I am wondering if there is an efficient way to solve the following question.
We have 2 groups of buckets, which is represented by number arrays. The number is the bucket size. The bucket size and the ...
0
votes
0
answers
27
views
How to get job sequencing problem answer in java?
I am not able to get the correct answer for the folowing question . I saw other approaches but i want to see the mistake i did .I used greedy method to solve the question .Can anyone tell what is ...
0
votes
0
answers
38
views
Minimise the maximum difference between any 2 elements of an array
You are given an array and an integer k. How to minimise the maximum difference between any 2 elements of array by changing atmost k elements to any number.
eg: 4,7,4,7,4 and k=2
Change element at ...
0
votes
0
answers
12
views
How to output the of the Genetic algorithm for RSU Deployment in python
actually i have developped a genetic algorithm for RSU(road side unit) deployment using python. i took the map from OSM converted to .net.xml and used in python. but after the algorithm execussion i ...
0
votes
0
answers
26
views
List index out of range (Fractional Knapsack)
I'm attempting to implement a greedy algorithm for the fractional knapsack problem for a coursera assignment. The course insists on not giving the inputs that cause the problem. Below is my code of ...
0
votes
0
answers
69
views
Dividing rocks into minimum number of groups
Given a list of rocks' weights and an integer maxVariance, divide the rocks into groups such that within a group the difference in weight between any two rocks is less than or equal to maxVariance. ...
0
votes
1
answer
65
views
'Steal minimum number of items as a thief' problem
One of the professors of mine asked this question;
Imagine a thief entering a house. In the house, there are infinitely many items
that can have only one of three different weights: 1 kg, 3 kgs, and 5 ...
-3
votes
1
answer
99
views
Getting a signed integer overflow on a Leetcode problem [closed]
I am trying the problem : 1833. Maximum Ice Cream Bars from Leetcode:
It is a sweltering summer day, and a boy wants to buy some ice cream
bars. At the store, there are n ice cream bars. You are ...
-3
votes
1
answer
128
views
applying non-zero offset 4 to null pointer [closed]
There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon ...
0
votes
2
answers
53
views
Into which technique would this algorithm fall into? Brute Force or Greedy?
I have an algorithm that I am not sure whether to classify as a greedy algorithm or a brute force algorithm.
while(true) {
int n = 0;
int d = 0;
int r = 0;
...
0
votes
0
answers
42
views
Cannot find symbol error in my minimum absolute difference pairs algorithm [duplicate]
Below is my implementation of the minimum absolute difference pairs algorithm.
import java.util.*;
public class Greedy{
public static void main(String args[]){
int A[]={4,1,8,7};
...
0
votes
2
answers
174
views
greedy and recursive algorithm for finding shortest path for all nodes in a complete binary tree with node and edge weights
I have a setup like this
The first part of the question is to implement a function that generates a complete binary tree (i.e. two arrays) with a given size as input where the node and edge weights ...
1
vote
3
answers
77
views
How can i use greedy algorithm to allocate products to stores
I got assigned to solve this problem: Given number of products sold in specific stores, is there a way to find from which stores to buy all products with the condition of buying only one product from ...
0
votes
0
answers
36
views
Greedy Graph coloring based on reinforcement learning
Can anyone please let me know if there are any graph based reinforcement learning environments (like networkx for normal graph problems). My aim is to develop a reinforcement learning environment for ...
0
votes
0
answers
16
views
Can an activity problem with unknown start time be solved with a greedy algorithm?
Given the classic activity problem of maximizing the number of activities in a given interval where t has to be smaller than k. However, in this case, the interval does not start before we select the ...
0
votes
0
answers
56
views
greedy and optimal solution for maximum sub interval in certain range
I tried to get first a greedy solution for me handling reservation buy getting 2 days (start, end) and getting the maximum days that can be reserved without the interval being overlap
#include <...
0
votes
0
answers
15
views
Min Makespan Algorithm [duplicate]
I have pseudocode for the algorithm I am trying to implement provided below...
greedy_min_make_span(T, m):
# T is an array of n numbers, m >= 2
A = [Nil, ... , Nil] # Initialize the assignments ...
0
votes
0
answers
40
views
How to output result of set cover algorithm as integers in python instead of 'None'?
I am having problems getting the output of a function to be displayed properly.
As can be seen in this image, what should be in place of the 'None' should be integers. The first, for example should ...
0
votes
0
answers
87
views
Problem of the traveler in the desert, greedy and dynamic approach
A traveler in a desert wants to go from one oasis to another until a final destination without taking the risk of dying from thirst (i.e. lack of water). He know the position of all the oases from his ...
0
votes
1
answer
97
views
Greedy Makespan algorithm
I am needing to implement this greedy algorithm in python, but am having trouble understanding how to find the 'processor' for which M[j] is the least. Algorithm provided below...
greedy_min_make_span(...
0
votes
0
answers
20
views
Product of N'th odd numbers without any loop
I faced a question where "You are supposed to find out the product of odd integers without using any loop or it generates runtime error.
Tried using loops and expecting without loops
0
votes
0
answers
31
views
scheduling events using shortest duration as greedy algorithm
There is a list of events and I want to schedule maximum number of events in a day in a way that they don't conflict with each other and the events are scheduled based on short duration events being ...
0
votes
2
answers
227
views
Assigning color to nodes in a graph such that no two neighbor nodes to it has same color
If you see the above graph, no nodes next to each other has the same color. I created a grid graph with diagonal edges across nodes using networkx python and applied greedy color to it.
greed = nx....
0
votes
1
answer
38
views
Largest Perimeter Triangle Leetcode Problem Python
I have given the mentioned problem quite a thought but was not able to come up with a working solution on my own. So I found the following solution, but I want to understand why does it work. Here it ...
1
vote
1
answer
206
views
Acyclic undirected graph allocation problem
We have an allocation problem: each node is a fuel source, and every edge contains a number of evenly spaced out lamps (think of them as being 1 m apart from each other). Each fuel source can power ...
0
votes
0
answers
76
views
Efficient algorithm for job sequencing, but with variable times needed
Problem: Given N tasks with potentially non-unique deadlines d1,...,dN and time needed t1,...,tN to complete each one (in hours), output a schedule that maximizes the number of deadlines met. Only 1 ...
0
votes
1
answer
218
views
Minimum of maximums for k-size nonconsecutive subsequence of array
Suppose I have an array, arr = [2, 3, 5, 9] and k = 2. I am supposed to find subsequences of length k such that no two elements in each subsequence are adjacent. Then find the maximums of those ...
0
votes
1
answer
91
views
What algorithm can be used to schedule meetings based on availability
Given:
A dictionary of availabilities and meeting times, where
key: person's name
value: [start time(inclusive), end time(exclusive), duration]
Start time & end time are denoted by integer >= 0
...
0
votes
1
answer
41
views
A* search algorithm with an example
I am investigating the A* search algorithm, and came across this example:
The description of the algorithm is as follows:
Visiting node 0 with currently lowest priority of 8.0
Updating distance of ...
0
votes
2
answers
309
views
Python Welsh-Powell graph coloring
I have implemented algorithm for Welsh-Powell graph coloring.
Task is that you have txt document with lines of 2 numbers, in which the first one represent vertex and the second one represent its ...
0
votes
0
answers
67
views
Confusion in epsilon greedy policy
I am trying to understand epsilon greedy policy but I am facing the following doubt.
The epsilon greedy policy is such that we select the action according to the following rule:
argmax Q(s,a) with ...
2
votes
1
answer
49
views
Minimum number of jumps II
I am trying to solve the GeeksForGeeks problem Minimum number of jumps:
Given an array of N integers arr[] where each element represents the max length of the jump that can be made forward from that ...
0
votes
0
answers
31
views
implementation and coloring graph
i try to implement and color a graph from a text file in python. but i don't know well the principes. in the file we have 3 types of lignes but we have to ignore the one that bigins with c.i select p(...
0
votes
0
answers
100
views
Find any local peak in 2D Matrix INCLUDING DIAGONAL NEIGHBOURS
Please do not close as duplicate, unless it actually is one, friends!
There are many posts on Stackoverflow for finding a peak or all peaks in a 2D matrix with distinct values and boundaries ...
1
vote
2
answers
68
views
Creating the greedy algorithm using recursion
For an assignement I have to write a Greedy Algorithm using a recursive function, but I can't seem to figure out how to do this.
The assignement is to make a route to go from one city to another, each ...
1
vote
0
answers
115
views
Greedy algorithm visualization
I have a problem which goes as follows.
There are n items. Each item i takes m_i time to manufacture and t_i time to test. Obviously, an item must be manufactured before being tested. At any point of ...
1
vote
1
answer
778
views
Given an array of houses find how many segments exists after n queries
I recently just encountered a leetcode style programming problem and I was wondering what the most optimal way to solve it is. The question goes like this:
Given an array of houses like houses = [1,2,...