|
Could you implement any of these ways and show me how it's done? Because I understood some of the things you've said but the rest I couldn't tbh 
|
|
|
|
|
As I wrote already, there are many articles about it. There are articles on this very website, for example Knapsack Bitwise. geeksforgeeks.org has articles about it. The wikipedia article is so complete that you can implement it straight from there. Medium.com is spammed full of Knapsack articles, just about any programmer transitioning from beginner to intermediate feels qualified to write them. You can read any of them, or any other articles about the subject, you don't need me - not yet. When you've tried it, and you still need help, then let's talk about it.
|
|
|
|
|
I've read a lot of articles believe me, I wouldn't ask for help re-writing the code if I didn't check every possible solution or article, that's why I'm asking for someone to re-write it to see how can I:
1- re-write recursion code to non-recursion code.
2- non-recursion solution for the knapsack problem.
|
|
|
|
|
iNoor72 wrote: I'm asking for someone to re-write it
You keep saying this but you refuse to understand that nobody is going to do your work for you. Do you have any idea how times a day people show up here and ask to have someone do their homework for them?
IT'S NOT GOING TO HAPPEN.
You cannot just "rewrite this code as a for loop". That doesn't work at all. Forget the code you have and start over using the resources you've been given.
|
|
|
|
|
Are you saying that you want the recursive solution rewritten into a non-recursive one?
Then you have two main alternatives: Either find a completely different algorithm for solving the same task.
Or do it by recursion, by maintaining your own recursion stack, e.g. in an array. The only reason for doing it that way would be because your programming language doesn't allow recursion - but I haven't seen that limitation since the days of Fortran 
I'll admit you a secondary reason for being a little careful with recursion: If your estimate for maximum recursion depth is way off, you may experience a stack overflow. In principle, you have the same situation with your array-as-recursion stack, but as you explicitly move stack pointers (i.e. calculate array indexes), it will be far more visible to you, so that you can avoid a fatal crash. You may set up an exception handler for a "real" stack overflow as well, but usually you have a hard time getting back onto your feet with no loss of data or code flow.
|
|
|
|
|
I've read that any recursion program can be written in non-recursion manner unless there's dynamic allocation in that recursion method, and I want to apply that on this particular code because I tried doing it by myself but again, not having a good programming background made me stop and couldn't do it myself.
|
|
|
|
|
iNoor72 wrote: not having a good programming background made me stop
So now would be a good time to learn programming properly, rather than trying to rewrite something that you do not understand.
|
|
|
|
|
Trying to evade the problem that you don't understand recursion by rewriting it to non-recursion is never going to work.
In my university days, a fellow student realized that he did not fully master recursion - termination in particular. So he defined a small programming problem for himself. After solving the task, he never had any problems with how to terminate a recursion. I think he made an excellent "programming etude", and have spread it out to a lot of people. It goes like this:
When you enter the recursive function, you write a line with the number of spaces given by the recursion depth, and then an asterisk. When you leave the recursive function, you do the same. The top level call gives parameters for (a) the maximum recursion depth, which you dive right into, (b) an intermediate recursion depth that you return to, before again recursing to the maximum depth, and (c) the number of times to recurse to the maximum depth and back to the intermediate level, before finally returning to the top level call (i.e. the number of "peaks").
For a call with arguments (5, 3, 3) the ouput should look something like
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*The problem statement seems very simple (and it is, for a seasoned recursionist). For an inexperienced programmer, you can usually hear a lot of cursing and re-cursing during the testing
|
|
|
|
|
I don't think that message was meant for me.
|
|
|
|
|
Pass it up the recursion stack! 
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
No, it was meant as a side-by-side answer to yours, supporting what you wrote.
So it was primarily meant for the originial poster. But it is a good exercise in recursion. Lots of (even experienced) programmers are touching recursion only occasionally, and then often in a quite simplistic way. So I propose it to any programmer.
If you think it so trivial that you can do it ten minutes, then spend those ten minutes proving to yourself that you master recursion. I have met several experienced programmers who thought it would be simple and straightforward, but experienced it to be "somewhat more tricky" than they at first thought it would be.
|
|
|
|
|
Very interesting, but the person that the message was meant for is unlikely ever to see it.
|
|
|
|
|
If only five other people read it, say "Hey, that I can do in ten minutes", go ahead to show it and they are still fiddeling around with termination conditions after half an hour, I think it has been worth it.
You are probably right about the original poster, and nothing seems to indicate that he will be ready to take on the task for some time.
|
|
|
|
|
Member 7989122 wrote: say "Hey, that I can do in ten minutes"
Making such statements is guaranteed to cause failure. I have done plenty of basic recursion functions but never anything very complicated. So I understand the concept, but the practical application always requires considerable thought.
|
|
|
|
|
Member 7989122 wrote: When you enter the recursive function, you write a line with the number of spaces given by the recursion depth, and then an asterisk. When you leave the recursive function, you do the same.
If the first value is 5 then the first line should be 5 spaces and then the asterisk, then 4 spaces asterisk ... (ignoring the second two parameters).
*
*
*
*
*
*
*
*
*
*
*
|
|
|
|
|
I'd like to see the code.
|
|
|
|
|
I made my solution 35+ years ago, and the source might still exist on one of the approx 100 eight-inch floppy disks, with a proprietary formatting and a proprietary file system, that I'm still keeping in a box in my basement. The manufacturer went bankrupt in 1992. I think that we were programming in Pascal at that time, so I would have to obtain a Pascal compiler to verify the code.
The cost&effort of recovering the source code (if it is available on one of the floppies, and the floppy is still readable) would be much larger than the cost of developing it anew. I could do it; you could do it yourself. The solution is really tiny, but the devil is in the details. Once the details are right, you'll say: Well, of course that's how it should be.
I might give it a try (maybe 35+ years of coding experience will make it appear simpler), but I haven't got the time right now. Go ahead yourself!
|
|
|
|
|
Member 7989122 wrote: I might give it a try (maybe 35+ years of coding experience will make it appear simpler), but I haven't got the time right now.
Same here, although coming up for 55 years. One day soon ... 
|
|
|
|
|
Hi All,
I would ask if there any opensource version of telnet client library(encrypted) available for windows
|
|
|
|
|
|
I have a MFC Application, where I am creating a new feature.
The new feature is to write a structure around size 900 KB to a file on disk every second. Similarly, my another application will read the same file every second after some time.
My questions are:
1. How to save the structure (900 KB) to the file in reduced size format, such that the file size doesn't become too big?
2. Saving the structure every second data as an individual file for reading and writing (there will be 60 files for 60 seconds)
or saving the structure sequentially in the same file(only one file)...Which is efficient for reading and writing
Please note that I am going to write the structure to the file for 4 days as a maximum period.
|
|
|
|
|
Quote: 1. How to save the structure (900 KB) to the file in reduced size format, such that the file size doesn't become too big?
It depends on the data. A general compression algorithm is probably not reccomended here, because you have to access fast the struct. So, it is up to you (based on data knowledge) to implement (if feasible) an ad hoc compression/decompression algorithm.
Quote: Saving the structure every second data as an individual file for reading and writing (there will be 60 files for 60 seconds)
or saving the structure sequentially in the same file(only one file)...Which is efficient for reading and writing
At first glance the individual file option looks more promising. But, again, data knowledge could change such an estimate.
|
|
|
|
|
Unless you have a lot of software experience, consider posting your specification (i.e. the actual problem that you're trying to solve). It might be that there are better approaches than having to write, and later read, a 900KB file every second.
|
|
|
|
|
manoharbalu wrote: Please note that I am going to write the structure to the file for 4 days as a maximum period.
4 days is 345,600 seconds. Are you saying that you are going to write 311 gigabytes of data to disk in 4 days? (That is if you don't find a good way to compress it.)
I certainly would not want to manage a single 311 GByte file. Nor would I want to manage 345,600 files ...
Writing a megabyte per second to a modern disk is nothing to worry about. A modern processor could easily handle compression of a megabyte a second, too. A disk to handle a third of a terabyte is no problem. You don't need any super-technology to get this to work. I would be more worried about either handling a 300 GByte file, or a third of a million tiny files (yes, by modern standards, files < 1Mbyte are "tiny").
Compressing to save space is just a technical detail - at application level, you realate to it at its uncompressed size. That comes natural if data are, say, a video stream, but then you would never consider to spread it over a third of a million files. So I am really curious to hear about the nature of the data!
I am not shaing CPallini's sceptisism to general compression algorithms. They work by the principle of recognizing recurring patterns, representing them by a shorter codeword. In totally unprocessed data there is often a large share of repeated patterns, especially in logging data. And in all sorts of readable text. Either, you'll come quite some way using a general method (such as pkzip), or it takes lots of detail knowledge of the information structures to do it much better.
Obviously, if you data is a known media type, such as video, photo or sound, then the mehtods have already been developed; you can get hold of a library to do it - I am thinking of when you to handle you own datatypes for which no dedicated compression method is yet known. Try out general methods first. Only if the results are completely unsatifactory, the files still way too large, may you consider making something of your own. Maybe you can reduce the data volume before you send it to compression, factoring out information elements, omitting data that can be reconstructed from other data etc.
Also consider whether you need losslss compression. If these 900 kB chunks are individual log entries, will they ever later be addressed as individual entries? Maybe you can reduce the data to statistics - averages, sums, whatever. (Like, when you swipe your card at the grocery store, the 49 individual entires on your checkout slip is reduced to a single total sum.)
Giving specific advice would be a lot easier with some details about the nature of the data you want to store.
|
|
|
|
|
Putting aside the data storage constraints mentioned by others, you need to experiment.
1) Is the structure bitwise copyable?
2) If so, just write it to disk using CFile and measure the impact.
2a) Use LZ4 to compress the data first (My own guess is that this would make a difference with a hard drive, but may actually take more time with an SSD.)
3) If not, you will need to serialize it; I'd still keep all the data binary.
3a) You could serialize it to a block of memory and then write that in one go (very likely the fastest way)
3b) You could serialize to a file using CStdioFile (depending on the data, this could be very slow. Even slower if you used C++ iostreams.)
3c) Do a combination; Serialize the data in 32k chunks and write them, perhaps asynchronously. (That said, when doing anything comparable, I prefer just having a second thread write synchronously.)
If the data needs to be future proofed, consider serializing using RapidJSON (which is a very fast C++ JSON library), compressing the result with LZ4 and then writing that. However, this could easily take longer than a second, depending on what the data is.
Edit: If the data is fairly regular, you might be able to save the full thing every ten seconds and differences in between. This can be tricky; I once worked on an app which did this and I found that the differencing alone exceeded the time it took to transmit the data over TCP.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
