Hi,
I need help with creating an algorithm to solve the problem below in the most efficient manner (efficiency in this case means low processing, not memory)
(Disclaimer: I studied discrete maths as part of my university course, but this was many years ago and I have forgotten most of the correct syntax. Sorry!)
Imagine we have
Set A (1,2,3,4,5,6,7, 8,9,10,11,12,13 ,14,15,16,17,18 ,19,20)
Set B (3,3,4,5,5,5,5, 5,6,6,7,8,12)
Set C
(
Set C.A (1,2) = 10
Set C.B (1,4,3) = 15
Set C.C (3,4,5) = 20
Set C.D (3,3,4,5) = 25
Set C.E (5,6) = 10
Set C.F (5,5,6) = 10
Set C.G (3,3,4,5,5,5,5, 5,6,6,7,8,12) = 5
)
B is a subset of A
C is a subset of A
I need to find
1) Which C are in B
2) What is the best combination of C. (Best means the biggest value i.e. C.A is worth 10, C.B is worth 15 etc)
When a C is found in B; B is to be reduced by C (e.g. if C.G is applied to B, there will nothing left in B)
A single instance of C can be applied to B a number of times (e.g. C.E above is in B twice)
Assume I have done 1 and the method is called GetApplicableSe ts(SetB) and the example above would return C.C, C.D, C.E, C.F, C.G
How do I do 2?
7 6564
Lets clean up some things first.
A Set contains unique elements. So B can't be called a Set.
Also could you describe what Set C is all about. What elements make up Set C and what does Set C.A (1,2) = 10 mean?
Hi r035198x,
What I mean with B is a subset of A. (is that all of the values in C must be in A).
What I am trying to get regarding C is that there are many of them, some have a higher value (to give this context I am working with money). So I want the BEST* combinations of C.
*BEST - as in the highest values when added together.
Another way of putting it is I am trying to find the combination of C.x sets which together are a subset of B, with the highest summed values. Am I making sense yet?
Further investigation has led me to Knapsack Problem and Subset sum problem. What I am trying to do is related to these but is subtly different I think.
Thanks for taking the time of reading my post.
Please read my post again and respond to what I have posted.
You need to be able to explain the problem using the correct terminology if you are going to get help.
Perhaps you should get a text/tutorial that explains the right terminology and read up that first and then you can polish up your description.
Sorry, can you tell me the parts that I am not describing very well?
Instead of sets, think of them as arrays
JosAH 11,448
Recognized Expert MVP @PeteSpeed
Please re-read what you have posted: set C isn't shown so your entire example doesn't make sense. Please preview before you post.
kind regards,
Jos
jkmyoung 2,057
Recognized Expert Top Contributor
So A is all items
B has a certain quantity of each member in A.
C is a set of groups of quantities of each member in A. Linear Programming:
Call N.A the number of times you use C.A, N.B the number of times you use C.B, etc..
Let V.A be the value of C.A, V.B be the value of C.B etc, Maximize Sum(for all i) N.i * C.i
where:
R1: N.A + N.B <= 0
R2: N.A <= 0
R3: N.B + N.C + 2N.D + 2 N.G <= 2
R4: N.B + N.C + N.D + N.G <= 1
etc.. for all 20 elements of A.
And N.A, N.B, ... >= 0
Note that you have mutltiple optimal answers with values of 45
N.D = 1, N.E = 2 down the line to
N.D = 1, N.F = 2
=============== ==
There's all sorts of algorithms you can use to find local maximums, generally based on some sort of greedy algorithm. Some of these steps may be harder to program than others, so pick and choose which ones you want to use.
I would advise first, optimizing the problem. Eliminate any variables which are unnecessary.
Step 1 Elimination: eliminate any elements which can't be used.
Leaves us with (3,4,5,6,7,8,12 )
Step 2 Eliminate unnecessary elements.
3 is only used when 4 is also used.
ratio of 3:4 is from 1 - 2 in all sets of C
ratio of 3:4 in set B is 2
So whenever we use a 4, we use at most 1 3.
-> We can eliminate element 3
4 is only used whenever 5 is also used.
ratio of 4:5 in set B is 1/5
ratio of 4:5 in sets of C ranges from 0 - 1
1 > 1/5, we cannot eliminate 4 yet.
etc..
we eliminate elements 7, 8 and 12 in this way also. This leaves us with
B' (4,5,5,5,5,5,6, 6)
C.C' (4,5) = 20
C.D' (4,5) = 25
C.E' (5,6) = 10
C.F' (5,5,6) = 10
C.G' (4,5,5,5,5,5,6, 6) = 5
Step 3: Minimize sets.
If we did this from the get go, in real life situations, the odds are low that there would be many sets to meaningfully reduce. However, after element minimization, we can remove some of the reduced sets.
After this optimization, we can also see that sets C.C', C.F', and C.G' are unnecessary.
C.D' is contained within C.C', and has equal or higher value
C.E' is contained within C.F', and has equal or higher value
C.F', is contained within C.G', and has equal or higher value.
Repeat Step 2 and Step 3 as much as necessary. Then solve.
B' (4,5,5,5,5,5,6, 6)
C.D' (4,5) = 25
C.E' (5,6) = 10
From here, you can easily get N.D = 1, N.E = 2
Hope something in this helps.
Sign in to post your reply or Sign up for a free account.
Similar topics |
by: Helene Pinol |
last post by:
Dear All
I have a problem to insert elements in a combination of containers.
Here is the declaration of the container I would like to use:
vector< set<myElement> > myContainer(vectorSize,set<myElement>());
The size of the vector is known but not yet the sizes of the different
sets.
Within a for loop, I build some myElements and try to insert them in
the correct set with:
myContainer.insert(myElement);
|
by: Bo Xu |
last post by:
Object of Combination
By Bo Xu
Introduction
A combination of n things, taken s at a time, often referred as an
s-combination out of n, is a way to select a subset of size s from a
given set of size n. There are n!/(s!(n-s)!) ways to do this. Donald
E. Knuth gives several methods (algorithms) to generate all the
s-combinations in . In such procedure-oriented way, each
s-combination is processed while it's being generated. In some
|
by: dskillingstad |
last post by:
I'm building a tracking system and I'm having some problems. I thought
this was relatively easy, but....
I have the following tables and fields (abbreviated):
tblPermitMain
PermitID - pk
ApplicantID (from tblApplicant)
PropertyID (from tblProperty)
PermitNumber
PermitApprovalDate
|
by: Anonieko Ramos |
last post by:
ASP.NET Forms Authentication Best Practices
Dr. Dobb's Journal February 2004
Protecting user information is critical
By Douglas Reilly
Douglas is the author of Designing Microsoft ASP.NET Applications and
owner of Access Microsystems. Doug can be reached at
doug@accessmicrosystems.com.
--------------------------------------------------------------------------------
|
by: Andy Fish |
last post by:
Hi,
I am about to commence the design of what will turn out to be a fairly large
asp.net web app, and I am looking for any good advice and resources (books,
web pages) concerning how best to structure it.
I would consider myself an experienced software designer and technical
architect - I certainly know enough to know that I don't know everything,
and I'm keen to pick up on current best practice. I have architected large
server apps...
| |
by: Mike Labosh |
last post by:
In VB 6, the Form_QueryUnload event had an UnloadMode parameter that let me
find out *why* a form is unloading, and then conditionally cancel the event.
In VB.NET, the Closing event passes a CancelEventArgs that lets me cancel
the Close() operation, but is there still any way to find out *why* a form
is closing?
This app as a form that needs to be loaded at startup, closed only at
shutdown, and then Show() / Hide() for the user. If...
|
by: Louis Aslett |
last post by:
I hope this is the correct newsgroup for this query (if not please
give me a pointer to where is best):
I understand the theory of normalisation etc and am trying to follow
best practices in the design of the database for a new project, but I
am unsure as to the best practice when one wants to store data
relating to combinations of arbitrary numbers of sets of data. For
example, take the following two groups of sets, each containing...
|
by: kivan.maharaj |
last post by:
What I want to do is write a program to test lexicographical
combinations of various sets of numbers to a predefined number and
write that true values to a text file.
Example:
Number choosen between 1 and 50
Number set = 6
|
by: Prateek |
last post by:
I have 3 variable length lists of sets. I need to find the common
elements in each list (across sets) really really quickly.
Here is some sample code:
# Doesn't make sense to union the sets - we're going to do
intersections later anyway
l1 = reduce(operator.add, list(x) for x in l1)
l2 = reduce(operator.add, list(x) for x in l2)
l3 = reduce(operator.add, list(x) for x in l3)
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
| |
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
| |
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |