algorithm to find best combination

Assume that I have a list of 100 products, each of which has a price. Each one also has a energy (kJ) measurement.

Would it be possible to find the best combination of 15 products for under $10 of which the sum of the energy (kJ) was greatest, using programming?

I know C#, but any language is fine. Cheers.

Update: Having a bit of troble finding some sample source code for the knapsack issue. Does anyone have any or know where to find some. Been googling for a few hours and need to get this sorted by tomorrow if possible. Ta.

From stackoverflow

• http://en.wikipedia.org/wiki/Knapsack_problem

• That sounds a lot like the knapsack problem. There are various approaches (order descending by energy density, for example).

• This reminds me of the famous knapsack algorithm

  http://en.wikipedia.org/wiki/Knapsack_problem

• This sounds more like a linear programming problem.

  Informally, linear programming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model and given some list of requirements represented as linear equations.

  Check out the Simplex Method.

  Lieven : +1 Spot on. Check out lp_Solve. It is opensource, does what you need and has examples for a myriad of languages, including C#.

  Mitch Wheat : @Lieven: Thx, and here's the link: http://lpsolve.sourceforge.net/5.5/

  Schotime : Won't this just give me the average price that the 15 products should be, not all the different prices which add to $10.

• This in Integer Linear Programming, optimizing a linear equation subject to linear constraints, where all the variables and coefficients are integers.

  You want variables includeItem1, ..., includeItemN with constraints 0 ≤ includeItem*i* ≤ 1 for all values of i, and includeItem1 + ... + includeItemN ≤ 15, and includeItem1*priceItem1 + ... ≤ 10, maximizing includeItem1*kilojouleItem1 + ....

  Stick that in your favorite integer linear program solver and get the solution :)

  See also http://en.wikipedia.org/wiki/Linear_programming

  It doesn't make sense to say that your particular problem is NP-complete, but it's an instance of an NP-complete (kind of) problem, so there might not be a theoretically fast way of doing it. Depending on how close to optimality you want to get and how fast ILP solvers work, it might be feasible in practice.

  I don't think you problem is a special case of ILP that makes it particularly easy to solve. Viewing it as a knapsack-like problem, you could restrict yourself to looking at all the subsets of 1..100 which have at most (or exactly) 15 elements, which is polynomial in n---it's n-choose-15, which is less than (n^15)/(15!), but that's not terribly useful when n = 100.

  If you want recommendations for solver programs, I have tried glpk and found it pleasant to use. In case you want something that costs money, my lecturer always talked about CPLEX as an example.

  Schotime : Thanks Jonas. Could you go through the setup a bit more with the variables and constraints. I've never done this before so any extra help would be greatly appreciated

  Jonas Kölker : You have three variables per item: one is {0, 1} and indicates whether the variable is included in your set; the second is the price of the item, the third is the energy. You then want to maximize the linear combination of "included" times "energy", subject to upper bounds on two other linr combns

  Jonas Kölker : s/variable/item/ at "is included in your set"

• This is the knapsack problem if you can either pick a product or not. If you can pick fractional values of products then you could solve this with the simplex method, but the fractional knapsack problem has a simple solution.

  Order the items by energy/price ratio, picking 100% of the highest ones until you run out of money, then pick a fractional value of the highest remaining one.

  For example if prices are 4,3,5,4 and energies are 3,5,2,7 the ordering is

  7/4, 5/3, 3/4, 2/5

  So you would pick items 4 and 2 which would cost 7$, with the 3$ remaining you would buy 75% of the first item for a price of $3 and an energy of 3*.75 = 2.25

  This would give a total energy of 14.25

  Note that allowing fractional values will give you a higher objective value than only allowing 0% or 100%, so no integer solution will do any better than 14.25 (or 14 for that matter since the objective value has to be an integer).

  To solve the original knapsack problem, you can use a branch-and-bound which should work just fine in practice. Assume that you have a current candidate solution with an objective value of z*

  1. Solve the relaxed problem, where you allow the fractional weights. If the value is less than z*, discard this branch.
  2. Compute a new value z which is the solution found without the last fractional weight, if this value is greater than z* , replace z* with your new value
  3. Pick one item (say the first in the list, the most profitable one) and form two subproblems, one where you must include it in the solution and one where you cannot include it in the solution (this is the branching step).
  4. As long as you have subproblems left to solve, pick one and go back to step 1.

  Note that when you create the subproblem where you must pick an item, just subtract its price from the budget and add the value to the profit, now you have a smaller problem to solve.

  For a more detailed description look at Branch and Bound on Wikipedia.

  Schotime : Thanks Pall but you can't add a fractional product. You either add it or you don't.

  Pall Melsted : It's still useful to "pretend" you could do it, since it gives you an upper bound on how well you could do. The branch and bound always keeps track of the best integer solution, it uses the fractional solution to reject branches that can't give you better than what you already have.

• The Stony Brook Algorithm Repository lists implementations for the knapsack problem.

  Their book The Algorithm Design Manual has this kind of information for a vast array of problems.

• It should be possible to solve the problem with Cream for Java. There's also a version for C# available CSharpCream.

• Yes, as everyone pointed out this is a complex knapsack problem. Something this simple might be good enough though...

  SELECT TOP 15 *
  FROM Product
  WHERE Price < 10
  ORDER BY Energy DESC
  

Regex not returning 2 groups

Hello everyone,

I'm having a bit of trouble with my regex and was wondering if anyone could please shed some light on what to do.

Basically, I have this Regex:

\[(link='\d+') (type='\w+')](.*|)\[/link]

For example, when I pass it the string:

[link='8' type='gig']Blur[/link] are playing [link='19' type='venue']Hyde Park[/link]" 

It only returns a single match from the opening [link] tag to the last [/link] tag.

I'm just wondering if anyone could please help me with what to put in my (.*|) section to only select one [link][/link] section at a time.

Thanks!

From stackoverflow

• Regular Expressions Info a is a fantastic site. This page gives an example of dealing with html tags. There's also an Eclipse plugin that lets you develop expressions and see the matching in realtime.

• You need to make the wildcard selection ungreedy with the "?" operator. I make it:

  /\[(link='\d+')\s+(type='\w+')\](.*?)\[\/link\]/
  

  of course this all falls down for any kind of nesting, in which case the language is no longer regular and regexs aren't suitable - find a parser

  annakata : I had to change some other aspects of the regex for it to make sense to my ecmascript brain...

  fishkopter : Thanks alot! works perfectly!

  Tomalak : @annakata: I think this question would have been a reasonable candidate for the "regexhtmlparserquestions" tag you once put up. ;-)

  annakata : sigh, I do miss that tag :)

  Tomalak : There is still one question that has it. You can still go for the Taxonomist badge. :-)

• You need to make the .* in the middle of your regex non-greedy. Look up the syntax and/or flag for non-greedy mode in your flavor of regular expressions.

Reporting Services 2005: ReportExecution2005.asmx returns with 401 Access Denied when called from a RenderingExtension

Hi,

I've got a rendering extension for reporting services which uses the ReportExecution2005.asmx service to execute a number of "subreports" and then puts the results in a powerpoint presentation.

A typical usage scenario would be to go to the Report Manager, select my "Powerpoint" report, which is used only as a placeholder for parameters to be passed to the "subreports". I then select my extension from the list of export formats and click Export, which runs the extension and it gives me back my pptx file.

This works fine on both our live and test servers. But I've run into a very weird problem trying to set up another test server.

Any call made by the extension to the webservice returns with "401 Access Denied" (no further substatus information available).

Things I've tried without success: - allow physical access to the folder structure of the ReportServer virtual directory to everyone. And I mean literally everyone - ASPNET, NETWORK SERVICE, Everyone, the account I usually use to log in, which is an admin and owner of the folder - use reporting manager to set up the security on the reporting services side. Again, every conceivable user/group account which could be involved was given every conceivable role. - allow anonymous access to the ReportServer web app. - enabled impersonation on the ReportServer web app. - hardcoded the user credentials to use when calling the webservice (by default it just uses System.Net.CredentialCache.DefaultCredentials)

I also made a little test website which consumes the ReportExecution service in exactly the same way as the RenderingExtension, and from the website, the web server authenticates fine and allows me to call the web service, so obviously the problem doesn't lie with the web service security setup itself.

Starting to pull my hair out. As a last resort, I'm about to reinstal Reporting Services, but in the mean time (or if that doesn't help) - if anyone has encountered something similar, I'd greatly appreciate any input.

From stackoverflow

• Hi,

  I have seen similar behavior when migrating an ASP.NET project which called the ReportExecution2005 web service. When running on my local box, everything was Ok. When I migrated it to our development server, I started getting 401 errors. In our case, Kerberos needed to be configured on the development server to delegate credentials to the SSRS box.

  You might want to verify that the new server will delegate it's credentials to the SSRS machine and see if that makes any difference.

  Hope this helps,

  Bill

Constructor chaining with "this"

Why does the first constructor in ClassA cause the compiler error 'cannot use "this" in member intializer'?

... or how can i get this to work?

Thanks

public sealed class ClassA : IMethodA
{
    private readonly IMethodA _methodA;

    public ClassA():this(this)
    {}

    public ClassA(IMethodA methodA)
    {
        _methodA = methodA;
    }

    public void Run(int i)
    {
        _methodA.MethodA(i);
    }

    public void MethodA(int i)
    {
        Console.WriteLine(i.ToString());
    }
}

public interface IMethodA
{
    void MethodA(int i);
}

From stackoverflow

• You are allowed to use the this(...) syntax to invoke another constructor at the same level - however, you cannot use this (the current instance) in this context.

  The easiest option here is to duplicate the assignment code (_methodA = methodA).

  Another option might be null-coalescing:

  public ClassA():this(null)
  {}
  
  public ClassA(IMethodA methodA) 
  { // defaults to "this" if null
      _methodA = methodA ?? this;
  }
  

  Bobby Cannon : @Marc Gravell: beat me to it...

• This is called out in section 10.11.1 of the C# spec

  An instance constructor initializer cannot access the instance being created. Therefore it is a compile-time error to reference this in an argument expression of the constructor initializer, as is it a compile-time error for an argument expression to reference any instance member through a simple-name.

  There is no way to get this to work with an instance constructor because this cannot be accessed. What you could do is make the constructor private, create an initialization method and a static constructor.

  public sealed class ClassA : IMethodA {    
    private ClassA() { }
    private void Initialize(IMethodA param) { ... }
    public static ClassA Create() {
      var v1 = new ClassA();
      v1.Initialize(v1);
      return v1;
    }
    public static ClassA Create(IMethodA param) {
      var v1 = new ClassA();
      v1.Initialize(param);
      return v1;
    }
  }
  

• You're trying to pass the object before it is constructed. Although the compiler could do something sensible in this case, in general that won't work.

  Your actual example works if you just do this:

     public ClassA()
    {
      _methodA = this; 
    }
  

  But you probably want to share more logic, so just use a function.

    public ClassA()
    {
      SetStuff(); 
      _methodA = this; 
    }
  
    public ClassA(IMethodA methodA)
    {
      SetStuff(); 
      _methodA = methodA;
    }
  

  Marc Gravell : Note that you can still use SetStuff with readonly fields... *if* you use a `ref` / `out` argument. Whether it is worth it depends on the scenario.

• You can't use the this keyword when chaining constructors essentially because this refers to an object that hasn't been instantiated yet (creation of the object doesn't begin until some (the top-level or base) constructor block has been entered). Moreover, why exactly would you want to do this? It seems rather pointless when you have access to the this keyword everywhere.

  I recommend simply using independent constructors as such:

  public sealed class ClassA : IMethodA
  {
      private readonly IMethodA _methodA;
  
      public ClassA()
      {
          _methodA = this;
      }
  
      public ClassA(IMethodA methodA)
      {
          _methodA = methodA;
      }
  }
  

  Perhaps I misunderstand what you're trying to do, but hopefully that will solve the issue for you.

Regular expression match only if subpattern doesn't match

Hello

I'm trying to match C style comments form a file, but only if the comment don't start with a certain labels introduced by @

For example from

/* some comment to match */
/* another comment.
this should match also */
/*@special shouldn't match*/

Is this possible using regular expressions only?

I'm trying this using JavaScript implementation of regular expressions.

From stackoverflow

• You could start with something like this:

  /\*[^@]
  

  But in general, you don't watch to match C-style comments with regular expressions, because of nasty corner-cases. Consider:

  "foo\" /* " " */ "
  

  There's no comment in that code (it's a compile-time concatenation of two string literals), but you're not going to have much luck parsing it without a real parser. (Technically, you could use a regular expression, because you only need a simple finite state machine. But it's a very disgusting regular expression.)

  Tomalak : +1 for pointing out the risky part. I don't think you could use a regular expression to successfully parse a C like language, though. Not even with an extremely ugly one.

  emk : Even though you can't parse arbitrary C code with a regex, you can actually strip comments. I've actually written a state machine before to do this before, and any such state machine can be translated into a regex. But I don't think I could construct it by hand without a lot skull sweat.

• /\*\s*(?!@)(?:(?!\*/).)*\*/
  

  Breaks down as:

  /\*               // "/*"
  \s*               // optional space
  (?!@)             // not followed by "@"
  (?:               // don't capture...
     (?!\*/).       // ...anything that is not "*/"
  )*                // but match it as often as possible
  \*/               // "*/"
  

  Use in "global" and "dotall" mode (e.g. the dot should match new lines as well)

  The usual word of warning: As with all parsing jobs that are executed with regular expressions, this will fail on nested patterns and broken input.

  emk points out a nice example of (otherwise valid) input that will cause this expression to break. This can't be helped, regex is not for parsing. If you are positive that things like this can never occur in your input, a regex might still work for you.

  Ant : Just to be pedantic, \s*(?!@).? doesn't mean what you think it means, but is rather a 0 width negative lookahead. It means that once you have matched as much whitespace as possible (\s*) continue with the match ONLY IF the next character is NOT an @. The .? is unnecessary.

  Tomalak : Just to be pedantic, how do you suppose I could have written a negative look-ahead without knowing what it is? ;-) You are right about the ".?" being unnecessary, though. I removed it.

• use negative lookahead

SQL backlog calculation (MS Access)

Hi, I need to calculate the backlog from a table: components(ProductId, ComponentId, Status, StatusDate) where ComponentId, Status and StatusDate are the primary key. ProductId is a foreign key. Example:

prod1, comp1, 01, 05/01/2009
prod1, comp1, 02, 05/01/2009
prod1, comp1, 03, 06/01/2009
prod1, comp1, 01, 07/01/2009
prod1, comp1, 02, 20/01/2009
prod2, comp2, 01, 22/01/2009
prod1, comp1, 02, 23/01/2009
prod1, comp1, 03, 31/01/2009

Basically what I am trying to calculate is the number of Components per week in status lower than 03. End user will introduce an interval date so I need to show all the weeks in the interval even if there is not backlog for a week. Expected result when end user introduces 01/01/2009-22/01/2009:

Week, Backlog
1,NULL/0
2,1
3,1
4,2

Explanation for Week 2: comp1 reach status 03 in the week but then goes back to status 01
Any help is more than welcome, thanks

From stackoverflow

• This is a partial answer in that I do not see where week 3 (11-18 Jan 2009) is coming from in your example. It illustrates the use of a counter table to get a line for missing values.

  SELECT Counter,WeekNo, CountofStatus FROM Counter LEFT JOIN
      (SELECT Format([StatusDate],"ww") AS WeekNo, COUNT(c.Status) AS CountOfStatus
      FROM components c
      WHERE c.StatusDate BETWEEN #1/1/2009# AND #1/22/2009#
      AND c.Status<3
      GROUP BY Format([StatusDate],"ww")) Comp
  ON Val(Comp.Weekno)=Counter.Counter   
  WHERE Counter.Counter>=Val(Format(#1/1/2009#,"ww"))
  AND Counter.Counter<=Val(Format( #1/22/2009#,"ww"))
  

  Remou : So the status is continuous and only marked at date changed? If so, my example does not suit.

  Remou : Your example shows two components, do you have a set number of components and is it large?

• I'm guessing a bit as to what you're trying to do, but here's my best guess:

  First, you should have a calendar table in your database:

  CREATE TABLE Calendar (
       calendar_date DATETIME NOT NULL,
       week_number INT NOT NULL,
       CONSTRAINT PK_Calendar PRIMARY KEY CLUSTERED (calendar_date)
  )
  GO
  
  INSERT INTO Calendar (calendar_date, week_number) VALUES ('1/1/2009', 1)
  INSERT INTO Calendar (calendar_date, week_number) VALUES ('2/1/2009', 2)
  etc.
  

  You can add additional columns to the table based on your business needs. For example, an "is_holiday" bit column to track whether or not your office is closed that day. This table makes so many different queries trivial.

  Now for your problem:

  SELECT
       CAL.week_number,
       COUNT(DISTINCT C.component_id)
  FROM
       Calendar CAL
  LEFT OUTER JOIN Components C ON
       C.status_date = CAL.calendar_date AND
       C.status IN ('01', '02')
  WHERE
       CAL.calendar_date BETWEEN @start_date AND @end_date
  GROUP BY
       CAL.week_number
  

  I used the IN for the status since you're using strings, so "< '03'" might not always give you what you want. Is '1' less than '03' in your mind?

  Also, if there is a time component on any of your dates the equality and BETWEEN checks might need to be tweaked.

  EDIT: I just saw the comments on the other answer. If you are dealing with just status changes, then the following query should work, although there may be a more performant method:

  SELECT
       CAL.week_number,
       COUNT(DISTINCT C.component_id)
  FROM
       Calendar CAL
  LEFT OUTER JOIN Components C ON
       C.status_date <= CAL.calendar_date AND
       C.status IN ('01', '02')
  LEFT OUTER JOIN Components C2 ON
       C2.component_id = C.component_id AND
       C2.status_date > C.status_date AND
       C2.status_date <= CAL.calendar_date
  WHERE
       CAL.calendar_date BETWEEN @start_date AND @end_date AND
       C2.component_id IS NULL
  GROUP BY
       CAL.week_number
  

  I'm not sure where the product fits in with all of this though.

What's the correct terminology for this design pattern?

I am writing a section of code that allows "soft" forms, such as a configurable questionnaire or checklist. The header table/class just groups together a bunch of questions, where each question has a "Text" property for the question itself, an "AnswerType" enumeration (string/boolean/StronglyAgree-StronglyDisagree) etc., an order property and whatever other little bells and whistles; you get the picture. And actual instances of the questions being answered can likewise be saved in relation to the question set as opposed to having hard-coded columns.

The details are actually unimportant. My question is: what is this design pattern called? What would be an appropriate name for the tables that are storing the soft-coded questions?

I thought of "SoftForm", which probably comes closest to describing the situation, but I've never heard of such a term before, and I'm sure there's a standard term for this design pattern. What is it?

From stackoverflow

• It seems like a flavor of Model-View-Controller, as applied to forms. Though the view and controller are probably fused together in your particular example, which is why it is hard to see.

  • Model is the data for the form.
  • View is responsible for visualizing the form data to the user.
  • Controller is responsible for handling the users' answers.

• ISPF called them panels, HTML and XAML calls them forms, Win32 Dialog resources. They all are interpreted, declarative UIs. "declarative UI" is probably the term you want, though what name to use for the DB table is up to you, since you're restricting yourself to a domain specific vocabulary (questionnaires) rather than being general purpose examples.

  If you're instead talking about implementing it, then there are several patterns. Some systems effectively interpret the declarative language by parsing in into an object graph (builder pattern). Other systems take the declarative specification, and generate code from that, and run it, either at run-time or when the configuration changes (some JSPs, a couple of systems I've built). You can use standard UI patterns such as MVC within the implementation of either the generative or the object graph approach.

• Sounds like a Builder pattern to me.

  Shaul : Nope. Builder pattern has a strongly defined interface. This is completely soft-coded, down to the questions and answers.

  chaos : The form isn't the Builder; the code that generates the form representation from the configuration data is. It has a 'strongly defined interface'. The forms aren't an 'interesting pattern' in themselves; the interesting thing about them is that they're dynamically generated to spec.