|
Hi Everyone!!
I have a list of objects, each one has a weight and a value.
So an array like this
[ [O1, V1, W1], [O2, V2, W2] ... [On, Vn, Wn]]
The goal is to get the sublist of objects with the highest value without exceeding the weight limit.
So I get an array like this
[ [O1, O2, O4, O7], V, W]
where V = V1 + V2 + V4 + V7 and W = W1 + W2 + W4 + W7
and W <= Wmax and V is the highest possible value.
Of course, I can build all the valid lists and sort them.
But it may be long!
Is there a more efficient algorithm?
Thanks everyone for your consideration!
-- modified 1-May-19 17:06pm.
|
|
|
|
|
We are more than willing to help those that are stuck: but that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.
So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.
Sent from my Amstrad PC 1640
Never throw anything away, Griff
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
What I did:
1) I build a simple algorithm that gives an good approximation.
2) I searched algorithm to known problems close to mine.
I saw the ship Berthing problem, but it seems to be different.
What I search:
I want to know if my problem is a classic one (or close to). And so, if an algorithm has been published to solve it.
I didn't ask you to build a specific solution, but to help me to search in the right direction.
Thanks everyone for your consideration!
|
|
|
|
|
I shouldn't be telling you this, but the answers to your questions are Yes and No.
Yes this is a classic (I mean classical) problem (it has been extensively studied since 1897), and No there is no algorithm that can find an optimal solution in polynomial time (i.e. quickly enough). You should also be advised that if you do discover such an algorithm for this problem, you will earn the one million dollar prize put up by the Clay Mathematics Institute for being the first person to show that P = NP.
I suppose you want to know what this classical problem is called. But as OriginalGriff quite rightly said, you should think about whether there are any optimizations you can make to your simple algorithm. Such things generally involve noting under what circumstances can some aspect of the problem be simplified. One might, for example, investigate the circumstances that would lead you to conclude that item A will never be part of an optimal solution because you can always do better than item A if you were to replace it with a set of items B, C, ... that taken together are both lighter and more valuable than A. Or perhaps you could define some substitution arrangement that is more complicated than just swapping out one item for another item as you pack your … er … um …
knapsack.
|
|
|
|
|
...extensively studied since 1897
If you can give a precise year, it means this problem as a name.
...one million dollar prize put up by the Clay Mathematics Institute
So is's worth working on it! 
...I suppose you want to know what this classical problem is called.
Of course!
|
|
|
|
|
ChrisFromWales wrote: knapsack
That name-drop might have been a bit too subtle! 
Knapsack problem - Wikipedia[^]
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Sorry, I'm not familiar with the rules of this forum.
I don't know if you are interested in following my research on the resolution of my problem.
I plan to
* study in which case my problem can be reduced to a fractional knapsack problem;
* test different algorithms (greedy, branch and bound, genetics) and their relevance depending on the case.
Personally, when I help someone, I like him to tell me later the taken steps.
What about you? Do you want me to come back in a few weeks to tell you what steps I have taken?
So if you want to know, I'll come back to tell you about it. Otherwise, I keep it for myself.
Thanks again 
|
|
|
|
|
Thanks.
-- modified 2-May-19 10:18am.
|
|
|
|
|
Hi Everyone!!
I am working on logic for a Microcontroller that dynamically updates a screen via UART. The screen only accepts vector based commands to fill a coordinate with a square and a filled color. The command looks like so
fill x,y,h,w,<color>The PHP code I wrote so far takes the image and converts each pixel to the following format, However, there are tons of room for optimization. An idea I had was to take the image and find the most common color then set the whole screen to this color. Then find all pixel's within a given shade and make it the same color than that beings the fill command to a single command because it can then cover two squares by using the command x,y,2,1,<color>.
The goal is to generate the picture with lossy compression but without extremely affecting the image and as few FILL commands as possible.
It can be your own or someone else's algorithm.. just make it possible to redraw with least amount of commands
Examples of algorithms are like this.
Cycle through each pixel and neighboring pixels and if they are similar shade make them the same. Then find the most common color and set the background image to that color. then cycle through each pixel if it's not that background color fill in that color.
The least amount of times you have to cast the fill command to drop a pixel the better the algorithm!
A sample image that will be used is here
https://www.faichi.com/sites/default/fi ... %202_0.png[^]
In this case, the large portion of the map is gray, so its best to make that shade one distinct RGB565 color then set the image of the full background to that color using a single fill command.
Then cycle through each pixel and combine additional like colors to make the least amount of permutations to cast a fill command to fill a pixel or a subset of pixels.
When doing this without any compression you would have to cast nearly one fill command for each pixel and would take over 5 minutes to draw a screen which is not a doable solution however there should be a simple way to go upon this.
Sample PHP code.
<?php
$img = imagecreatefromjpeg("Path to Image that is 480x272");
$width = ImageSX($img);
$height = ImageSY($img);
for ($y = 0; $y < $height; $y++) {
for ($x = 0; $x < $width; $x++) {
$c = imageColorAt($img, $x, $y);
$r = ($c >> 16) & 0xFF;
$g = ($c >> 8) & 0xFF;
$b = $c & 0xFF;
$r = $r >> 3;
$g = $g >> 2;
$b = $b >> 3;
$oc = ($r << 11) | ($g << 5) | $b;
echo ("fill $x,$y,1,1,$oc<br>");
}
}
?>
If anyone has any Keyterms I may use to research this issue I'd be more then open to review them and any pointers in the right direction would be greatly appreciated!
Thanks everyone for your consideration!
modified 24-Apr-19 14:18pm.
|
|
|
|
|
|
Creating the output of the pixel's isn't exactly the part I am looking for guidance on but this is a useful read anyhow to keep on my radar. I think maybe I am looking for "image vectoring" perhaps? Im not sure if that the correct term.
|
|
|
|
|
There is 4x4 matrix type of bool (can be 0 or 1)
It looks like this e.g.:
(1)(1)(0)(0)
(1)(0)(0)(1)
(1)(0)(0)(1)
(1)(1)(0)(0)
That is input...
And output is list(array) of pairs of positions and that pair represents one area
for example
In first column there are four 1s, so it should return (0,0)&(0,3) (1x4)
After that step then it becomes:
[1](1)(0)(0)
[1](0)(0)(1)
[1](0)(0)(1)
[1](1)(0)(0)
that means that 1s are used
After that you can do (0,3)&(1,0) (it's 2x2)
And that means that group can pass over like it's folded paper(when iterating use i%4)
Also that means 1s that are used can be used again
[1][1](0)(0)
[1](0)(0)(1)
[1](0)(0)(1)
[1][1](0)(0)
And do that over and over until all 1s are used
There are rules:
- All 1s must be used
- Same 1s can be used more than once
- Width and height must be power of 2 (1,2,4)
that means groups can be (1x1,2x1,1x2,2x2,4x2,2x4,4x1,1x4,4x4) - Group can cross over border to get to the other side
(like folded paper; 0 can be connected with 3 and vice versa) - Logically number of areas should be minimum possible
- Area is defined by it's top left corner and it's bottom right corner
(In form of point) - Optional:
The times one [1] is used more than once must be maximum possible
Output for this example:
(0,3)&(1,0)
(3,1)&(0,2)
Also output can be done with more areas but this is only using two and it's wanted solution
There is example of one interesting matrix:
(1)(0)(1)(1)
(1)(0)(1)(0)
(1)(0)(1)(0)
(1)(0)(1)(1)
Output:
(3,3)&(0,0)(that means that all 4 corners are included in one area)
(0,0)&(0,3)
(2,0)&(2,3)
Another:
(0)(1)(1)(1)
(0)(1)(0)(1)
(1)(1)(0)(1)
(0)(0)(0)(0)
Output:
(0,2)&(1,2)
(1,1)&(1,2)
(1,0)&(2,0)
(3,0)&(3,1)
(3,1)&(3,2)
Preferable languange is any C type (C C++ C#)
|
|
|
|
|
Very interesting, but what is your question? If you are expecting someone here to write your homework assignment, then I am afraid you will be disappointed.
|
|
|
|
|
My question is:
Is there any idea I can start from I tried finding every group for each [one] left...
but it takes 16 ifs...
Also this is not my homework I'm just trying to implement algorithm of
"minimization of switching function" for digital circuits with visualising it so I need that output
|
|
|
|
|
Sorry, no idea. What algorithm is it supposed to follow?
|
|
|
|
|
|
I would try a "classifier".
Flatten it out to a 16 column "record".
4x4 is manageable; you should be able to construct your own "training data" with all combinations.
You then run your "sample" against the training data and have it "classify" your (flattened) matrix by comparing columns.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
I would start by writing classifiers for all sub-sizes:
1x1 (trivial)
2x2
3x3
4x4
The previous level may be placed inside the next level in one of 4 positions, possibly allowing the creation of additional output lines. IOW, use recursion!
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows.
-- 6079 Smith W.
|
|
|
|
|
I work for a milk company and I have to deliver Milk to stores. I also have to pick up expired milk when there is some. Is there an algorithm or process that can track the sales and expired product to predict future sales and minimize the amount of expired product picked up?
|
|
|
|
|
I was wondering a problem from algorithm - Proving that a particular matrix exists - Stack Overflow[^] Somebody said that there is a solution found by a computer, but I was unable to find a proof.
Prove that there is a matrix with 117 elements containing the digits such that one can read the squares of the numbers 1, 2, ..., 100.
Here read means that you fix the starting position and direction (8 possibilities) and then go in that direction, concatenating the numbers. For example, if you can find for example the digits 1,0,0,0,0,4 consecutively, you have found the integer 100004, which contains the square numbers of 1, 2, 10, 100 and 20, since you can read off 1, 4, 100, 10000, and 400 (reversed) from that sequence.
But there are so many numbers to be found (100 square numbers, to be precise, or 81 if you remove those that are contained in another square number with total 312 digits) and so few integers in a matrix that you have to put all those square numbers so densely that finding such a matrix is difficult, at least for me.
I found that if there is such a matrix mxn, we may assume without loss of generality that m<=n. Therefore, the matrix must be of the type 1x117, 3x39 or 9x13. But what kind of algorithm will find the matrix?
I have managed to do the program that checks if numbers to be added can be put on the board. But how can I implemented the searching algorithm?
|
|
|
|
|
Hi all,
I want to calculate the number of labels available on a roll.
Please help me to found the exact formula.
Thanks
|
|
|
|
|
|
I'm working on formulating an optimization problem to find the minimum weighted tree between a set of terminals (aka Steiner tree). The literature on Steiner tree formulations consider the set of terminals as input, and provides the minimum weighted tree connecting them (possibly also including non-terminal transit nodes). However, the structure of my problem requires these set of terminals to be decided "in conjunction with" the minimum Steiner tree between them. Hence, existing Steiner tree formulations based on cut-sets, multi-commodity flows, etc., are not applicable in my case, given lack of prior knowledge about the set of terminals.
Any suggestions on how to design a linear program for Steiner tree where the set of terminals is not provided as an input, and at best can be denoted by a set of decision variables?
|
|
|
|
|
The problem is the following:
Given N containers with different sizes between 1 and N (2 <= N <= 10^5), each of them placed in a line, determine how many places can be freed if one container can be placed in another only if its size is less that the others size and they don't have any other containers between them. Multiple placings can be made, so if there are containers placed in each other, they can be placed in another container (if the bottom container size is less than the others size), a container can be placed in another group of container (if its size is less than the top container size), and a group of containers can be placed in another group of containers with similar rules.
Example: if N = 8 and the containers are placed in the following order: 1 8 2 4 3 6 7 5, then 7 places can be freed; we place 3 in 4, then 2 in 3, 6 in 7, 5 in 6, 4 in 5, 7 in 8, and 1 in 2. This way all the containers can be packed in a single group.
My idea of solving this problem is the following: calculate the minimum difference between all the neighbour containers sizes, then find the first pair where this minimum appears and make a placement. Then repeat the whole process again until no placements can be made. Then calculate the freed places.
This can be done trivially in quadratic time, but that is too slow. The other thing that bothers me that this method may not lead to the optimal solution.
Note: I have to implement the algorithm in C++, and my program has to finish in 200ms. This is why a quadratic solution has no chance. Also, I don't want to have my job done by others, I posted this because I got stuck solving the problem, and needed some help to know if my approach is correct or how can I make optimizations.
modified 24-Apr-22 21:01pm.
|
|
|
|
|
You set no limit on N, so there is no solution that will always "finish in 200 ms" ... (which is a long time) ... unless you add a timer; if it runs too fast.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
