|
Hello!
I have a set that contains maximum 10^6 items. All item are 4^n number, where 0 <= n <= 11, all items have a price that can be 1 <= price <= 10^8. And I also have another number k, where k is 4^n number and 0 <= n <= 11. The items are ordered monotonically first according to size of numbers, then to prices.
I want to take the sum of the items that equal to number k, and the price is minimal.
The example:
A := {16(1),16(2),16(3),16(4),64(11)}and k=64. (format: Number (price) -> 16(1))
So, the solution is 16(1),16(2),16(3),16(4), because 1+2+3+4=10 smaller then 11.
Any idea?
Thanks!
|
|
|
|
|
The problem and your notation aren't clear.
|
|
|
|
|
This sounds like a homework problem, and if so, you should consult with your instructor. As the other poster had said, your problem is not entirely clear, may want to rephrase it.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
|
|
|
|
|
Your problem sounds like the knapsack problem. 4^n just acts as item-id (given in this peculiar notation to confuse) while k is the capacity of the knapsack. Its easy to solve this problem using the method of dynamic programming. Brute-force approaches which rely on generating combination also exist.
|
|
|
|
|
Hi everybody.
I'm gonna make a Line Follower robot with PID algorithm (like this one[^])
I could calculate PID output , But I don't know how I have to use it.
output of PID = (P*Kp)+(D*Kd)+(I*Ki)
My robot have two motors.(Right motor and left motor)
Assume the out put of PID is 180, this number is for which one of motors ?(The range of my PWM is 0-255)
Do you understand me ?
Could you please guide me ?
|
|
|
|
|
How are you getting the feedback on the velocity of your motors? A difference in velocity between the right and left motors is what you're trying to control to compensate for how far away from the line you are. Also, how are you determining your position relative to the line?
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
Tim Craig wrote: How are you getting the feedback on the velocity of your motors?
I don't have any feedback, as I read we didn't need feedback on the velocity of motors.
Tim Craig wrote: Also, how are you determining your position relative to the line?
We have 5 sensors under the robot.(Our robot is in triangle shape)
I determine the position like this :
output of sensors | position
10000 | -4
11000 | -3
01000 | -2
01100 | -1
00100 | 0
00110 | 1
00010 | 2
00011 | 3
00001 | 4
|
|
|
|
|
For line following you can probably get by without it if your motors are reasonably well balanced. I see you found the article with the five photosensors and the assignment of the position relative to the line based on which ones are on. Your biggest hassle will be in getting the PID tuned.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
Tim Craig wrote: Your biggest hassle will be in getting the PID tuned.
Thanks Tim Craig.
Actually I've done it and I get the output of PID ( As I posted at the first )
But I don't know how I have to use the output !!!
There is an output , so how we have to apply it between motors ?
|
|
|
|
|
Hi,
just a guess: if the output of your PID is called RIGHT (positive to steer right, negative for left), then I would feed the motors something like this (assuming DC motors, not stepping motors):
rightOutput = speed - factor * right;
leftOutput = speed + factor * right;
Luc Pattyn
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
Thanks Luc Pattyn.
What are speed , factor variables?
I guess speed is maximum speed !!!
|
|
|
|
|
speed is speed, whatever speed you want to have. it is not maximum speed, and it could be variable.
factor is a factor, a coefficient, some constant, a value you have to choose.
Maybe I should refine to:
rightOutputVoltage = factor1 * speed - factor2 * right;
leftOutputVoltage = factor1 * speed + factor2 * right;
so you need factors to make the formula correct, as they convert speed (in m/s or whatever unit you choose) and PID output (in units unknown to me), into voltages.
Luc Pattyn
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
Luc Pattyn wrote: factor is a factor, a coefficient, some constant, a value you have to choose.
So can we set it to 1 ?
|
|
|
|
|
this is elementary math; assume right=0, then you see factor1 is the ratio of the voltage required to get a certain speed, so if 1 volt makes your robot travel at 1 meter per second, then factor1 = 1Vs/m
Luc Pattyn
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
how can we determine the output of PID=180 is in right position according to this case??
|
|
|
|
|
So you actually have the robot built? I thought you said you were going to build it. You can't really tune the PID until you have the hardware. If you don't understand what I mean by tune, there are hundreds of papers on the internet about it.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
Tim Craig wrote: Also, how are you determining your position relative to the line?
Do we have to determine the position base on Meter or Centimeter ?
|
|
|
|
|
No, you've already assigned values to your tape sensors. That's the input to the PID loop. The output is a signal to steer the robot to keep the tape centered, ie. the input signal is zero. It sounds like you have a typical two powered wheel differentilly steered robot so you steer by having one wheel turn at a different rate than the other. The robot will turn toward the slower wheel. Take the simple case of following a straight tape (if your robot won't follow a straight tape, you'll never follow a curving one. You start out with the same output set for both motors. If the robot drifts to the left, the right sensors will start to pick this up and you'll want to steer the robot back to the right. For practical purposes, this means slowing down the right motor since you can always slow down or even go into reverse. You can't always speed up if you're running at or near top speed. What you have to do is to tune the PID parameters so that the output tells you how much to slow the motor.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
From what you said, I thought you'd started with this article?[^]
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
|
I've done wire following (of machines weighing well over 2,000lbs). On larger-scale devices, the momentum of the machine becomes a major factor, but with smaller ones it will probably be less of one. Still, it would be helpful to know what mechanical control constraints you're operating under. Making a robot that will stay on the wire isn't too hard if hyper-sensitive steering is acceptable. Making the robot travel smoothly along the wire is harder.
At least on the larger machines I've worked with, getting a 'straight' PID to work well under all circumstances has generally proved difficult. Your situation may be further complicated by the fact that many PWM systems modulate motor current rather than voltage. Do you have dynamic breaking available? How is it controlled?
|
|
|
|
|
|
I am trying to Write a MATLAB code to scale the input image of 256x256 to a smaller image of 160x160 using the bilinear interpolation, the idea behind it is to compare it with the image resulted from the function imresize, Can anybody give me a detailed algorithm(preferably a pseudo code) on how to approach that.
I already have some links but they are so poorly commented that I get easily lost.
Any Help will be highly appreciated.
|
|
|
|
|
Hi,
this[^] seems pretty straightforward. What is the problem?
For all kinds of transformations, walk the new coordinate system, find the location in the old coordinate system, and apply the transformation, hence:
foreach yy in new coordinates
calculate y in old coordinates
round to neighbours y1 and y2
foreach xx in new coordinates
calculate x in old coordinates
round to neighbours x1 and x2
apply bilinear formulas
store result at (xx,yy)
next
next
Luc Pattyn
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
Do you have an idea how to do it in matlab, I am pretty new at that language and I need to program it in matlab, also I don't think it's that simple, the purpose is for image resizing, so basically it will be applied on a Matrix(not that it changes anything).
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
