|
I feel what he wants is to input two numbers n and m and the program should choose some numbers from series 1,2..n whose sum equals m and return all such combinations.
For n=10, m=8, the possible combinations are:
1+7
2+6
3+5
..
1+1+6
1+2+5
..
..
there can be a lot of such combinations.
This is probably the ideal candidate for DP?
1. store all possible ways to make 1 using numbers from given series and store them
2. likewise all possible ways to make 2. since 2 can only be either using it alone or 1+1 and then to make 1, you already have ways stored during step 1 and so on for oher nos. for 3 = 3, 2+1. use info. for ways to make 2 and you'll automatically get 3, 2+1, 1+1+1
for 4 = 4, 3+1...
|
|
|
|
|
Subset Sum problem
I am pasting an algorithm, got this from a book
Algorithm SumOfSubSet(s,k,r)
{
x[k] := 1;
if( s + w[k] = m ) then Write( x[1:k]);
else if( s + w[k] + w[k+1] <= m )
then SumOfSub( s + w[k], k+1, r-w[k]);
if( (s+r-w[k] >= m) and (s + w[k+1] <= m )) then
{
x[k] := 0;
SumOfSub( s, k + 1, r - w[k]);
}
}
s = is the sum to be generated
w is the set with size n,
x is an array and if x[i] is one means <code>ith element in w is in the subset
k is the index of element in w we are examining
r is the remaining sum that can be created from k +1th element to nth item in w
modified on Thursday, May 12, 2011 9:23 AM
|
|
|
|
|
Pleaze i need a help , i need an implementation for the subset sum problem using these algorithms
1. An exponential time exact algorithm
2. Fully polynomial-time approximation scheme
|
|
|
|
|
Hello people!
I am looking for a way to simulate movement of units along a path, i mean as you can see it in strategy games. The path consists of waypoints and i am looking for a method to make the units follow these with a somewhat life-like way, so no too sharp turns, try to evade collision with other units and so on. I tried to google it up but i am probably not using the correct search terms because i didn't find anything usefull really, so i thought i ask here, maybe you folks have the know-how, or at least know where or what i should look for.
Thanks in advance.
> The problem with computers is that they do what you tell them to do and not what you want them to do. <
> Sometimes you just have to hate coding to do it well. <
|
|
|
|
|
|
Thank you.
> The problem with computers is that they do what you tell them to do and not what you want them to do. <
> Sometimes you just have to hate coding to do it well. <
|
|
|
|
|
|
If you have the paths worked out (perhaps using some of the techniques shown in the very good selection of links posted above) then you might also be interested in steering behaviours - route following, collision avoidance, queuing, flocking etc. :-
http://www.red3d.com/cwr/steer/[^]
Days spent at sea are not deducted from one's alloted span - Phoenician proverb
|
|
|
|
|
Indeed i am, thank you for the help. 
> The problem with computers is that they do what you tell them to do and not what you want them to do. <
> Sometimes you just have to hate coding to do it well. <
|
|
|
|
|
I have little discrete spaces but they are non-Euclidean. May I still call them manifolds?
Tadeusz Westawic
An ounce of Clever is worth a pound of Experience.
|
|
|
|
|
I need some help as I am finding it hard to create a program that can make character shapes such as a triangle in a console application (C#):
*
***
*****
*******
As an example of what I would like to print, i.e. I want the triangle's height 4 and my program will draw a triangle as described.
This is so that I can improve on control structures, squares and rectangles are easy 
|
|
|
|
|
Total number of characters? Total number of stars? Total number of spaces? Half total number of spaces? Increment values? etc ...
It's time for a new signature.
|
|
|
|
|
Basically the way to approach this is to draw a rectangle like you did before but put some conditions in to determine if you should print a star or a blank.
First to get the width: Notice that except for the top line the triangle's width increases by 2 for each line it goes down.
Therefore: Width = (Height * 2) - 1
To determine whether to draw a star you need to find if you are close enough to the center of the triangle.
Center = Width / 2
On each line the triangle gets one wider in each direction so you need 2 variables to hold the range where stars should be drawn. So if you use Min and Max as your variable the should initally be set to Center and then subtract 1 from min each line you go down and add 1 to max each line you go down. You can then use these variable to test if your loop counter is between these 2 variables.
Hope this helps,
Mike
|
|
|
|
|
All,
I'm in need of an algorithm that I have no idea about comparing it to other algorithms.
Imagine if you had a set of wooden blocks, all the same thickness but differing in lengths. The goal is to stack all of the blocks in such a way that the total length of this "wall" is the shortest length possible. There would be a different result depending on if you stack the wall 2, 3, 4, or N blocks high.
The wall doesn't have to be perfectly straight on both sides either.
Not sure what this is even similar to, and would appreciate some guidance.
I'd also appreciate knowing where some of you look for information about algs, because it seems like I can never find a comprehensive site containing the names, applications and descriptions of common or more obscure ones. If any of you want to give up your sources, your secrets are moderately safe with me
Thanks,
Michael Fritzius
|
|
|
|
|
your problem seems somewhat similar to the Knapsack problem[^], and Wikipedia (or Google) are a good place to start your search.
|
|
|
|
|
|
It's similar to job scheduling, where the blocks are "jobs" (length of job = length of block) and the layers of the wall would represent the "machines" (number of layers = number of machines)
|
|
|
|
|
Are there some good algorithms following this approach?
I have been working in this area and would love to learn more.
|
|
|
|
|
IIRC Integer Linear Programming can solve it optimally, but everyone seems to use heuristic algorithms because solving an ILP problem is too slow for them. But ILP is not an algorithm but a way of specifying a problem. You can solve it with Branch and Bound (I may give it a try and see how slow it would really be).
It's quite annoying to search for good information about job scheduling with full in-advance knowledge - most papers about job scheduling deal with the online version and/or throw in some extra unknowns and restrictions.
|
|
|
|
|
harold aptroot wrote: veryone seems to use heuristic algorithms because solving an ILP problem is too slow for them
This is exactly what i found. Further, all algorithms that are created in this area are more of customized or proprietary.
Job Scheduling is a major and vast topic and solving it by usage of rectangles, is breaking down the problem into smaller problem. I hope to see such algorithms...
|
|
|
|
|
Time for some code!
This code is clearly crap, I just wrote it quickly in a console app to see whether it would work. It calculates the optimal solution with a simple branch and bound algorithm (without any tricks that can make it faster) - all cases that I tested worked.
For anything above 16 jobs it becomes really really slow. As a quick guestimate, the time complexity is about O(m^j) where m is the number of machines and j is the number of jobs.
static int[] Schedule(int[] jobs, int machines)
{
int[] targets = new int[jobs.Length];
int[] lengths = new int[machines];
_bestFoundScore = int.MaxValue;
_bestSolution = null;
_schedule(jobs, targets, 0, lengths);
return _bestSolution;
}
static int _bestFoundScore = int.MaxValue;
static int[] _bestSolution = null;
static void _schedule(int[] jobs, int[] targets, int index, int[] lengths)
{
if (index == jobs.Length)
{
int max = 0;
for (int j = 0; j < lengths.Length; j++)
if (lengths[j] > max)
max = lengths[j];
if (max >= _bestFoundScore)
return;
_bestFoundScore = max;
int[] res = new int[targets.Length];
Array.Copy(targets, res, res.Length);
_bestSolution = res;
}
else
{
for (int i = 0; i < lengths.Length; i++)
{
targets[index] = i + 1;
lengths[i] += jobs[index];
int max = 0;
for (int j = 0; j < lengths.Length; j++)
if (lengths[j] > max)
max = lengths[j];
if (max < _bestFoundScore)
{
_schedule(jobs, targets, index + 1, lengths);
}
targets[index] = 0;
lengths[i] -= jobs[index];
}
}
}
Edit: but I don't think using rectangles will help at all - if anything, it will just make it harder without having any benefits. The problem would still be the same, but you'd have "the width of a rectangle" instead of just "some integer or float" which is really just the same thing.
modified on Sunday, April 18, 2010 8:44 AM
|
|
|
|
|
Hey Harold,
Thanks for the code. This piece of code is basically an implementation of nested recursions. Usually, algorithms have been developed to use some shortcuts in order to achieve the optimum.
harold aptroot wrote: For anything above 16 jobs it becomes really really slow
It will get even slower if you add the type of jobs, type of machines, duration of job, efficiencies and duration of machine operation. I wonder what speed would be then.
The idea of rectangles is not to complicate the problem but to be able to see the problem differently.
Consider solving a maze from within the maze or sitting on the top of it. The perspective makes the whole of the difference. And hence the rectangle example. Another benefit is to represent the scheduling graphically and allow manual placement of pieces into a box of available resources.
Lets share in case we come across something. I have been trying to find something useful for a long time. When I saw your comment, I got optimistic
Cheers.
|
|
|
|
|
It has one shortcut - as soon as a partial solution becomes worse than the currently-best-found solution it bails out and starts on the next partial solution.
I tried adding a greedy approximation so it could discard more partial results in the beginning when it hasn't found a good potential solution yet, but on random problem instances with m=3 and j=20 it only helped slightly more than a third of a percentage on average (which is basically nothing)
|
|
|
|
|
buddy. we both know that nested recursions will ultimately be slow and they have one inherent problem "SCALING". you can't scale them. They are only good for small problems.
|
|
|
|
|
Yea I know, do you know anything better though?
4.5 seconds (in release mode) on average for m=3 j=20, btw (with that naive implementation)
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
