Tagged Questions
18
votes
7answers
2k views
Dynamic Programming algorithm to find Heavy integers
Recently I was asked the following question:
A non-negative integer is called heavy if the average value of its digits in decimal representation exceeds 7. For example the number 8698 is heavy, ...
13
votes
4answers
2k views
Dynamic programming in the functional paradigm
I'm looking at Problem thirty one on Project Euler, which asks, how many different ways are there of making £2 using any number of coins of 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
There ...
6
votes
5answers
631 views
Shortest sequence of unfold operations
I was proposed to solve this problem a while ago, and still keeps me woken up at unusual times:
Two integer variables L and R are given. Their initial content is 0
and 1, respectively, and it ...
6
votes
1answer
586 views
Dynamic algorithm for text auto-correct
I am writing an auto-correct program that uses the levenshtein distance to correct
a phrase of no more than 64 charcters based of a specific dictionary containing 8000 words.
The dictionary ...
4
votes
3answers
806 views
Dynamic Programming and Knapsack Application
Im studying dynamic programming and am looking to solve the following problem, which can be found here http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf:
You are given a rectangular piece of ...
4
votes
3answers
2k views
Dynamic Programming - making change
I'm having trouble figuring out my last section of code for a Dynamic Coin Changing Problem. I have included the code below.
I can't figure out the last else. Should I just use the greedy algorithm ...
4
votes
1answer
247 views
What kind of algorithm is this? Box packing/Knapsack?
I was working on an application last night and came across a particular problem which I'm sure probably has an efficient algorithm to solve it. Could anyone suggest?
Problem:
TL;DR: Maybe a picture ...
3
votes
3answers
1k views
kadane algorithm in java
I have the following implementation of Kadane's algorithm in java. It is basically to find the maximum sum of contiguous subarray.
String[] numbers = string.split(",");
int max_so_far ...
3
votes
1answer
757 views
What is Chain Matrix Multiplication?
I am trying to understand what is a chain matrix multiplication and how it is different from a regular multiplication. I have checked several sourcers yet all seem to be very academically explained ...
3
votes
2answers
384 views
how many ways can we place k rooks on a nxn chessboard safely
Given k rooks and a n by n chess board, the rooks can safely be placed on the board W different ways, where
W = k!(n C k)^2
written differently W = n!n!/(k!(n-k)!(n-k)!)
PROBLEM STATEMENT:
Write a ...
3
votes
3answers
677 views
How can I implement this equation in Java?
OK, this is more of a follow-up question: How to compute optimal paths for traveling salesman bitonic tour?
First of all, for the bitonic tour of the traveling salesman problem I have the following ...
3
votes
3answers
323 views
Counting no of matrices with exactly n/2 zeros and n/2 ones in each row and each column for a given n
For a blank n * n matrix, even n, we want to assign zeros and ones to this matrix so
that each row and each column contains exactly n/2 zeros and n/2 ones for a given n.
Can there be a Dynamic ...
3
votes
1answer
75 views
Longest zig-zag subsequence using dynamic programming
I need to write a method that needs to return the length of the longest subsequence of sequence that is a zig-zag sequence. The algorithmic approach should be dynamic programming.
A sequence of ...
3
votes
2answers
540 views
Knapsack Dynamic Programming
this is a typical Knapsack problem requiring dynamic programming and there is no constraint on the supply of items. I've been working on this for my class and I tried to play around with the algorithm ...
2
votes
4answers
132 views
Dynamic programming ArrayIndexOutOfBoundException
I'm getting this weird exception, I don't really understand why.. I tried debugging and found out that it goes wrong when running:
opt[i][j] = Double.POSITIVE_INFINITY;
and when i == 0 and j == 1, ...
