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

Answer 1

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.

Answer 2

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

Answer 3

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.Columns.Add("item", typeof(int));
            dt.Columns.Add("weight", typeof(double));
            dt.Columns.Add("volume", typeof(double));
            dt.Columns.Add("price", typeof(double));

            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));

            Console.ReadKey();
        }
        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"]));
        }
    }
}

Please see:

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)

Answer 4

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

Answer 5

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;

Answer 6

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.Columns.Add("item", typeof(int));
            dt.Columns.Add("weight", typeof(double));
            dt.Columns.Add("volume", typeof(double));
            dt.Columns.Add("price", typeof(double));

            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);

            Console.ReadKey();
        }
        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
        }
    }
}

Answer 7

Thanks it helped me :-) :-)

Answer 8

Thanks it helped me :-) :-)

You're welcome, thanks too for this nice issue.

Answer 9

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

http://social.msdn.microsoft.com/Forums/en-US/csharpgeneral/thread/5c67643e-ad07-4fd9-89ef-506c791cb0ec

Answer 10

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

http://social.msdn.microsoft.com/Forums/en-US/csharpgeneral/thread/5c67643e-ad07-4fd9-89ef-506c791cb0ec

Thank you. I'll take a look.