# find for total price • ### Question

• I have to find the maximum total price for the list of items so that
weight should not exceed 14285 and volume should not exceed 17..
I need the best algorithm to find this.. the structure look like this

wmax=    14285
vmax=    17

item    weight    volume    price
==============================
1    1190    1.3    240
2    1374    0.8    229
3    1031    1.7    425
4    1265    1.5    341
5    1218    1.8    177
6    1524    1.9    205
7    1842    0.8    100
8    367    1.3    486
9    1541    1.7    368
10    878    1    351
11    1058    1.1    260
12    2026    1    100
13    1808    1.8    290
14    1803    1.6    253
15    1411    0.7    100

• Edited by Thursday, April 15, 2010 4:28 AM
Wednesday, April 14, 2010 5:26 AM

• Thanks for ur answer it perfectly working bt i need output as i explained below.

c consider i enter N items...and each item has some weight volume and price...

i may get N items or N-1 items as the output it doesnot matter but sum of weight and volume of obtained items should not exceed the
prescribed value.... and the price of the obtained items should be high after all
permutations and combinations and transporter should get profit after all...so that he should come know what are the items he can trasport with best profit.

we should work on 3 constraints here

1.sum of weight of obtained items should not exceed 14285
2.sum of volume of obtained items should not exceed 17
3.price should be high after all permutations and combinations

hope u got some idea now

Nice question. you want to find optimal package based on package's price but with packaging limitations.

I provided an example which do this with O(2^N) where N is number of items. I am sure there is better solutions but I will do at my home tonight when I have more free time to coding. let's see the solution:

```using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
DataTable dt = new DataTable();

dt.PrimaryKey = new DataColumn[] { dt.Columns["item"] };

dt.Rows.Add(new object[] { 1, 1190, 1.3, 240 });
dt.Rows.Add(new object[] { 2, 1374, 0.8, 229 });
dt.Rows.Add(new object[] { 3, 1031, 1.7, 425 });
dt.Rows.Add(new object[] { 4, 1265, 1.5, 341 });
dt.Rows.Add(new object[] { 5, 1218, 1.8, 177 });
dt.Rows.Add(new object[] { 6, 1524, 1.9, 205 });
dt.Rows.Add(new object[] { 7, 1842, 0.8, 100 });
dt.Rows.Add(new object[] { 8, 367, 1.3, 486 });
dt.Rows.Add(new object[] { 9, 1541, 1.7, 368 });
dt.Rows.Add(new object[] { 10, 878, 1, 351 });
dt.Rows.Add(new object[] { 11, 1058, 1.1, 260 });
dt.Rows.Add(new object[] { 12, 2026, 1, 100 });
dt.Rows.Add(new object[] { 13, 1808, 1.8, 290 });
dt.Rows.Add(new object[] { 14, 1803, 1.6, 253 });
dt.Rows.Add(new object[] { 15, 1411, 0.7, 100 });

double wmax = 14285;
double vmax = 17;
DisplayBestPackaging(dt, wmax, vmax);

}
static void DisplayBestPackaging(DataTable dt, double wmax, double vmax)
{
//number of possible packages
UInt64 numberOfPossiblePackages = (UInt64)Math.Pow(2, dt.Rows.Count) - 1;

//searching for best package
UInt64 bestPackeageNumber = 0;
double bestPriceSum = 0;
double packagePriceSum, packageWeightSum, packageVolumeSum;
for (UInt64 packeageNumber = 0; packeageNumber <= numberOfPossiblePackages; packeageNumber++)
{
packagePriceSum = 0;    //for current packge
packageWeightSum = 0;    //for current packge
packageVolumeSum = 0;    //for current packge
int rowIndex = 0;   //index of item
//computing packageNumber items. e.g. packageNumber 0100011011b = items indices at 0,1,3,4,8 (1's positions)
for (; rowIndex < dt.Rows.Count; rowIndex++)
{
UInt64 rowBit = (UInt64)Math.Pow(2, rowIndex);  //item bit position
if ((rowBit & packeageNumber) != 0) //Does current packageNumber contains this item?
{
//computing because it's in package
packagePriceSum += Convert.ToDouble(dt.Rows[rowIndex]["price"]);
packageWeightSum += Convert.ToDouble(dt.Rows[rowIndex]["weight"]);
packageVolumeSum += Convert.ToDouble(dt.Rows[rowIndex]["volume"]);
if (packageVolumeSum > vmax || packageWeightSum > wmax)
break;
}
}
if (rowIndex >= dt.Rows.Count)  //for loop shouldn't break because of maximun exceedings
{
if (packagePriceSum > bestPriceSum) //Is it better than previous?
{
//register as best so far
bestPriceSum = packagePriceSum;
bestPackeageNumber = packeageNumber;
}
}
}

//displaying the founded best package
Console.WriteLine("Best Package Items:");
packagePriceSum = 0;   //for proof only
packageWeightSum = 0;   //for proof only
packageVolumeSum = 0;   //for proof only
for (int rowIndex = 0; rowIndex < dt.Rows.Count; rowIndex++)
{
UInt64 rowBit = (UInt64)Math.Pow(2, rowIndex);
if ((rowBit & bestPackeageNumber) != 0)
{
Console.Write("{0}, ", dt.Rows[rowIndex]["item"]);
packagePriceSum += Convert.ToDouble(dt.Rows[rowIndex]["price"]);
packageWeightSum += Convert.ToDouble(dt.Rows[rowIndex]["weight"]);
packageVolumeSum += Convert.ToDouble(dt.Rows[rowIndex]["volume"]);
}
}
Console.WriteLine();
Console.WriteLine("packageWeightSum={0}, packageVolumeSum={1}, packagePriceSum={2}", packageWeightSum, packageVolumeSum, packagePriceSum);   //for proof only
}
}
}
```
Wednesday, April 14, 2010 8:48 AM
• Thank you.

I provided an example which do this by LINQ technology:

```using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
DataTable dt = new DataTable();

dt.PrimaryKey = new DataColumn[] { dt.Columns["item"] };

dt.Rows.Add(new object[] { 1, 1190, 1.3, 240 });
dt.Rows.Add(new object[] { 2, 1374, 0.8, 229 });
dt.Rows.Add(new object[] { 3, 1031, 1.7, 425 });
dt.Rows.Add(new object[] { 4, 1265, 1.5, 341 });
dt.Rows.Add(new object[] { 5, 1218, 1.8, 177 });
dt.Rows.Add(new object[] { 6, 1524, 1.9, 205 });
dt.Rows.Add(new object[] { 7, 1842, 0.8, 100 });
dt.Rows.Add(new object[] { 8, 367, 1.3, 486 });
dt.Rows.Add(new object[] { 9, 1541, 1.7, 368 });
dt.Rows.Add(new object[] { 10, 878, 1, 351 });
dt.Rows.Add(new object[] { 11, 1058, 1.1, 260 });
dt.Rows.Add(new object[] { 12, 2026, 1, 100 });
dt.Rows.Add(new object[] { 13, 1808, 1.8, 290 });
dt.Rows.Add(new object[] { 14, 1803, 1.6, 253 });
dt.Rows.Add(new object[] { 15, 1411, 0.7, 100 });

double wmax = 14285;
double vmax = 17;
Console.WriteLine("Max Price For (wmax={0}, vmax={1}) Is {2}", wmax, vmax, GetMaxPrice(dt, wmax, vmax));

}
static double GetMaxPrice(DataTable dt, double wmax, double vmax)
{
return dt.AsEnumerable().Where(dr => Convert.ToDouble(dr["weight"]) < 14285 && Convert.ToDouble(dr["volume"]) < 17).Max(dr => Convert.ToDouble(dr["Price"]));
}
}
}```

http://msdn.microsoft.com/en-us/vcsharp/aa336746.aspx (101 LINQ Samples)

http://msdn.microsoft.com/en-us/vbasic/bb688086.aspx (LINQ To DataSet Samples)

Wednesday, April 14, 2010 7:27 AM
• Hi,

One more way to do it,

```            List<Item> Items = new List<Item>{
new Item{Itemid = 1, Weight = 1190, Volume = 1.3m, Price = 240},
new Item{Itemid = 2, Weight = 1374, Volume = 0.8m, Price = 229},
new Item{Itemid = 3, Weight = 1031, Volume = 1.7m, Price = 425},
new Item{Itemid = 4, Weight = 1265, Volume = 1.5m, Price = 341},
new Item{Itemid = 5, Weight = 1218, Volume = 1.8m, Price = 177},
new Item{Itemid = 6, Weight = 1524, Volume = 1.9m, Price = 205},
new Item{Itemid = 7, Weight = 1842, Volume = 0.8m, Price = 100},
new Item{Itemid = 8, Weight = 367, Volume = 1.3m, Price = 486},
new Item{Itemid = 9, Weight = 1541, Volume = 1.7m, Price = 368},
new Item{Itemid = 10, Weight = 878, Volume = 1.0m, Price = 351},
new Item{Itemid = 11, Weight = 1058, Volume = 1.1m, Price = 260},
new Item{Itemid = 12, Weight = 2026, Volume = 1.0m, Price = 100},
new Item{Itemid = 13, Weight = 1808, Volume = 1.8m, Price = 290},
new Item{Itemid = 14, Weight = 1803, Volume = 1.6m, Price = 253},
new Item{Itemid = 15, Weight = 1411, Volume = 0.7m, Price = 100}
};
decimal totalPrice = 0;
decimal maxWeight = 14285;
decimal volumeMax = 17;
Items.ForEach(delegate(Item item)
{
decimal maxVolumeAganistWeight = maxWeight / item.Weight;
decimal PriceForOneVolume = item.Price / item.Volume;
if (maxVolumeAganistWeight > volumeMax)
totalPrice += PriceForOneVolume * volumeMax;
else
{
totalPrice += PriceForOneVolume * maxVolumeAganistWeight;
}
});

Console.WriteLine("Total Price: {0}", totalPrice);

public class Item
{
public int Itemid { get; set; }
public decimal Weight { get; set; }
public decimal Volume { get; set; }
public decimal Price { get; set; }
}```

Regards,

Vinil;

Wednesday, April 14, 2010 7:47 AM

### All replies

• Welcome to MSDN, Aravinda.

Could you please put your current code which produce these data in a DataTable/CLR Object,...? I did your desired job by LINQ sooner if I had that code.

Thank you.

Wednesday, April 14, 2010 6:39 AM
• i am still trying it out to get the answer.. plz post if u have i need it urgently...

overall concept i have explained below

first i select all the items, in those i should select items so that weight of all the selected items should not exceed 14285 at the same time volume should not exceed 17 along with this the transporter should not get loss.mean to say he should should get maximum price...getting maximum price is the key factor

Wednesday, April 14, 2010 7:08 AM
• Thank you.

I provided an example which do this by LINQ technology:

```using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
DataTable dt = new DataTable();

dt.PrimaryKey = new DataColumn[] { dt.Columns["item"] };

dt.Rows.Add(new object[] { 1, 1190, 1.3, 240 });
dt.Rows.Add(new object[] { 2, 1374, 0.8, 229 });
dt.Rows.Add(new object[] { 3, 1031, 1.7, 425 });
dt.Rows.Add(new object[] { 4, 1265, 1.5, 341 });
dt.Rows.Add(new object[] { 5, 1218, 1.8, 177 });
dt.Rows.Add(new object[] { 6, 1524, 1.9, 205 });
dt.Rows.Add(new object[] { 7, 1842, 0.8, 100 });
dt.Rows.Add(new object[] { 8, 367, 1.3, 486 });
dt.Rows.Add(new object[] { 9, 1541, 1.7, 368 });
dt.Rows.Add(new object[] { 10, 878, 1, 351 });
dt.Rows.Add(new object[] { 11, 1058, 1.1, 260 });
dt.Rows.Add(new object[] { 12, 2026, 1, 100 });
dt.Rows.Add(new object[] { 13, 1808, 1.8, 290 });
dt.Rows.Add(new object[] { 14, 1803, 1.6, 253 });
dt.Rows.Add(new object[] { 15, 1411, 0.7, 100 });

double wmax = 14285;
double vmax = 17;
Console.WriteLine("Max Price For (wmax={0}, vmax={1}) Is {2}", wmax, vmax, GetMaxPrice(dt, wmax, vmax));

}
static double GetMaxPrice(DataTable dt, double wmax, double vmax)
{
return dt.AsEnumerable().Where(dr => Convert.ToDouble(dr["weight"]) < 14285 && Convert.ToDouble(dr["volume"]) < 17).Max(dr => Convert.ToDouble(dr["Price"]));
}
}
}```

http://msdn.microsoft.com/en-us/vcsharp/aa336746.aspx (101 LINQ Samples)

http://msdn.microsoft.com/en-us/vbasic/bb688086.aspx (LINQ To DataSet Samples)

Wednesday, April 14, 2010 7:27 AM
• Thanks for ur answer it perfectly working bt i need output as i explained below.

c consider i enter N items...and each item has some weight volume and price...

i may get N items or N-1 items as the output it doesnot matter but sum of weight and volume of obtained items should not exceed the
prescribed value.... and the price of the obtained items should be high after all
permutations and combinations and transporter should get profit after all...so that he should come know what are the items he can trasport with best profit.

we should work on 3 constraints here

1.sum of weight of obtained items should not exceed 14285
2.sum of volume of obtained items should not exceed 17
3.price should be high after all permutations and combinations

hope u got some idea now

Wednesday, April 14, 2010 7:45 AM
• Hi,

One more way to do it,

```            List<Item> Items = new List<Item>{
new Item{Itemid = 1, Weight = 1190, Volume = 1.3m, Price = 240},
new Item{Itemid = 2, Weight = 1374, Volume = 0.8m, Price = 229},
new Item{Itemid = 3, Weight = 1031, Volume = 1.7m, Price = 425},
new Item{Itemid = 4, Weight = 1265, Volume = 1.5m, Price = 341},
new Item{Itemid = 5, Weight = 1218, Volume = 1.8m, Price = 177},
new Item{Itemid = 6, Weight = 1524, Volume = 1.9m, Price = 205},
new Item{Itemid = 7, Weight = 1842, Volume = 0.8m, Price = 100},
new Item{Itemid = 8, Weight = 367, Volume = 1.3m, Price = 486},
new Item{Itemid = 9, Weight = 1541, Volume = 1.7m, Price = 368},
new Item{Itemid = 10, Weight = 878, Volume = 1.0m, Price = 351},
new Item{Itemid = 11, Weight = 1058, Volume = 1.1m, Price = 260},
new Item{Itemid = 12, Weight = 2026, Volume = 1.0m, Price = 100},
new Item{Itemid = 13, Weight = 1808, Volume = 1.8m, Price = 290},
new Item{Itemid = 14, Weight = 1803, Volume = 1.6m, Price = 253},
new Item{Itemid = 15, Weight = 1411, Volume = 0.7m, Price = 100}
};
decimal totalPrice = 0;
decimal maxWeight = 14285;
decimal volumeMax = 17;
Items.ForEach(delegate(Item item)
{
decimal maxVolumeAganistWeight = maxWeight / item.Weight;
decimal PriceForOneVolume = item.Price / item.Volume;
if (maxVolumeAganistWeight > volumeMax)
totalPrice += PriceForOneVolume * volumeMax;
else
{
totalPrice += PriceForOneVolume * maxVolumeAganistWeight;
}
});

Console.WriteLine("Total Price: {0}", totalPrice);

public class Item
{
public int Itemid { get; set; }
public decimal Weight { get; set; }
public decimal Volume { get; set; }
public decimal Price { get; set; }
}```

Regards,

Vinil;

Wednesday, April 14, 2010 7:47 AM
• Thanks for ur answer it perfectly working bt i need output as i explained below.

c consider i enter N items...and each item has some weight volume and price...

i may get N items or N-1 items as the output it doesnot matter but sum of weight and volume of obtained items should not exceed the
prescribed value.... and the price of the obtained items should be high after all
permutations and combinations and transporter should get profit after all...so that he should come know what are the items he can trasport with best profit.

we should work on 3 constraints here

1.sum of weight of obtained items should not exceed 14285
2.sum of volume of obtained items should not exceed 17
3.price should be high after all permutations and combinations

hope u got some idea now

Nice question. you want to find optimal package based on package's price but with packaging limitations.

I provided an example which do this with O(2^N) where N is number of items. I am sure there is better solutions but I will do at my home tonight when I have more free time to coding. let's see the solution:

```using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
DataTable dt = new DataTable();

dt.PrimaryKey = new DataColumn[] { dt.Columns["item"] };

dt.Rows.Add(new object[] { 1, 1190, 1.3, 240 });
dt.Rows.Add(new object[] { 2, 1374, 0.8, 229 });
dt.Rows.Add(new object[] { 3, 1031, 1.7, 425 });
dt.Rows.Add(new object[] { 4, 1265, 1.5, 341 });
dt.Rows.Add(new object[] { 5, 1218, 1.8, 177 });
dt.Rows.Add(new object[] { 6, 1524, 1.9, 205 });
dt.Rows.Add(new object[] { 7, 1842, 0.8, 100 });
dt.Rows.Add(new object[] { 8, 367, 1.3, 486 });
dt.Rows.Add(new object[] { 9, 1541, 1.7, 368 });
dt.Rows.Add(new object[] { 10, 878, 1, 351 });
dt.Rows.Add(new object[] { 11, 1058, 1.1, 260 });
dt.Rows.Add(new object[] { 12, 2026, 1, 100 });
dt.Rows.Add(new object[] { 13, 1808, 1.8, 290 });
dt.Rows.Add(new object[] { 14, 1803, 1.6, 253 });
dt.Rows.Add(new object[] { 15, 1411, 0.7, 100 });

double wmax = 14285;
double vmax = 17;
DisplayBestPackaging(dt, wmax, vmax);

}
static void DisplayBestPackaging(DataTable dt, double wmax, double vmax)
{
//number of possible packages
UInt64 numberOfPossiblePackages = (UInt64)Math.Pow(2, dt.Rows.Count) - 1;

//searching for best package
UInt64 bestPackeageNumber = 0;
double bestPriceSum = 0;
double packagePriceSum, packageWeightSum, packageVolumeSum;
for (UInt64 packeageNumber = 0; packeageNumber <= numberOfPossiblePackages; packeageNumber++)
{
packagePriceSum = 0;    //for current packge
packageWeightSum = 0;    //for current packge
packageVolumeSum = 0;    //for current packge
int rowIndex = 0;   //index of item
//computing packageNumber items. e.g. packageNumber 0100011011b = items indices at 0,1,3,4,8 (1's positions)
for (; rowIndex < dt.Rows.Count; rowIndex++)
{
UInt64 rowBit = (UInt64)Math.Pow(2, rowIndex);  //item bit position
if ((rowBit & packeageNumber) != 0) //Does current packageNumber contains this item?
{
//computing because it's in package
packagePriceSum += Convert.ToDouble(dt.Rows[rowIndex]["price"]);
packageWeightSum += Convert.ToDouble(dt.Rows[rowIndex]["weight"]);
packageVolumeSum += Convert.ToDouble(dt.Rows[rowIndex]["volume"]);
if (packageVolumeSum > vmax || packageWeightSum > wmax)
break;
}
}
if (rowIndex >= dt.Rows.Count)  //for loop shouldn't break because of maximun exceedings
{
if (packagePriceSum > bestPriceSum) //Is it better than previous?
{
//register as best so far
bestPriceSum = packagePriceSum;
bestPackeageNumber = packeageNumber;
}
}
}

//displaying the founded best package
Console.WriteLine("Best Package Items:");
packagePriceSum = 0;   //for proof only
packageWeightSum = 0;   //for proof only
packageVolumeSum = 0;   //for proof only
for (int rowIndex = 0; rowIndex < dt.Rows.Count; rowIndex++)
{
UInt64 rowBit = (UInt64)Math.Pow(2, rowIndex);
if ((rowBit & bestPackeageNumber) != 0)
{
Console.Write("{0}, ", dt.Rows[rowIndex]["item"]);
packagePriceSum += Convert.ToDouble(dt.Rows[rowIndex]["price"]);
packageWeightSum += Convert.ToDouble(dt.Rows[rowIndex]["weight"]);
packageVolumeSum += Convert.ToDouble(dt.Rows[rowIndex]["volume"]);
}
}
Console.WriteLine();
Console.WriteLine("packageWeightSum={0}, packageVolumeSum={1}, packagePriceSum={2}", packageWeightSum, packageVolumeSum, packagePriceSum);   //for proof only
}
}
}
```
Wednesday, April 14, 2010 8:48 AM
• Thanks it helped me :-) :-)
Thursday, April 15, 2010 4:25 AM
• Thanks it helped me :-) :-)
You're welcome, thanks too for this nice issue.
Thursday, April 15, 2010 4:47 AM
• even i have one more issue i have already posted.... that is

how i can call to mobile phone from windows application or asp.net application

• 