الحد الأقصى لقيمة الطوابع البريدية على مظروف

Question

مشكلة ختم البريد هي عبارة عن لغز رياضي يسأل ما هي أصغر قيمة بريد لا يمكن وضعها على مظروف ، إذا كان بإمكان الحرف أن يحمل عددًا محدودًا فقط من الطوابع ، وقد يكون لها فقط بعض قيم الوجه المحددة.

على سبيل المثال ، لنفترض أن المغلف يمكن أن يحتفظ فقط بثلاثة طوابع ، وقيم الطوابع المتاحة هي 1 سنت ، و 2 سنت ، و 5 سنتات ، و 20 سنتًا. ثم الحل هو 13 سنتا. نظرًا لأنه يمكن الحصول على أي قيمة أصغر مع ثلاثة طوابع على الأكثر (على سبيل المثال 4 = 2 + 2 ، 8 = 5 + 2 + 1 ، إلخ) ، ولكن للحصول على 13 سنتًا ، يجب على المرء استخدام أربعة طوابع على الأقل.

هل هناك خوارزمية بالنظر إلى أقصى قدر من الطوابع المسموح بها والقيمة الاسمية للطوابع ، يمكن للمرء أن يجد أصغر بريد لا يمكن وضعه على المظروف؟

مثال آخر:
يمكن استخدام 5 طوابع كحد أقصى
القيمة: 1 ، 4 ، 12 ، 21
أصغر قيمة لا يمكن الوصول إليها هي 72. يمكن إنشاء القيم 1-71 بمزيج معين.

في النهاية ، ربما سأستخدم Java لتدوين هذا.

Answer 1

نعم ، هناك مثل هذه الخوارزمية. بسذاجة: بدءًا من 1 ، جرب كل مجموعة ممكنة من الطوابع حتى نجد مزيجًا يعطي مجموع 1 ، ثم حاول 2 ، وهكذا. تنتهي الخوارزمية عندما تجد رقمًا بحيث لا يضيف أي مزيج من الطوابع إلى هذا الرقم.

على الرغم من أن بطيئًا ، لمشاكل صغيرة بما يكفي (على سبيل المثال 100 طابع ، 10 وظائف) يمكنك حل هذا بمقدار "معقول" من الوقت ...

ولكن ، بالنسبة للمشاكل الكبيرة ، تلك التي لدينا العديد من الطوابع المتاحة (على سبيل المثال 1000) والعديد من المواقف الممكنة (على سبيل المثال 1000) ، قد تستغرق هذه الخوارزمية وقتًا ممتعًا. هذا هو ، بالنسبة للمشاكل الكبيرة جدًا ، قد يكون الوقت المناسب لحل المشكلة باستخدام هذا النهج ، مدى عمر الكون ، وبالتالي فهو ليس مفيدًا لك حقًا.

إذا كانت لديك مشاكل كبيرة حقًا ، فأنت بحاجة إلى إيجاد طرق لتسريع بحثك ، وتسمى هذه السرعات الاستدلال. لا يمكنك التغلب على المشكلة ، ولكن يمكنك حل المشكلة بشكل أسرع من النهج الساذج من خلال تطبيق نوع من معرفة المجال.

قد تكون هناك طريقة بسيطة لتحسين هذا النهج الساذج هي أنه في أي وقت تجرب فيه مجموعة من الطوابع التي لا تساوي الرقم الذي تبحث عنه ، فإنك تزيل هذه المجموعة من المجموعة المحتملة لمحاولة أي رقم مستقبلي ، وتمييز هذا المستقبل رقم غير متوفر. قال بطريقة أخرى: احتفظ بقائمة من الأرقام التي وجدتها بالفعل والتوليفات التي أتيت لك هناك ، ثم لا تبحث عن هذه الأرقام أو مجموعاتها مرة أخرى.

Answer 2

هذه نصيحة أخرى: يمكن تشكيل كل مجموعة من الطوابع التي تضيف إلى بعض الأرقام المحددة عن طريق إضافة ختم واحد إلى مجموعة الحد الأدنى من الطوابع التي تضيف ما يصل إلى هذا الرقم.

على سبيل المثال ، لنفترض أن لدينا الطوابع 1 و 2 و 7 و 12 و 50 ، وحد من 5 طوابع ، ونريد معرفة ما إذا كان يمكن تمثيل 82. للحصول على هذا 82 ، يجب عليك إضافة:

• 1 إلى مجموعة من الطوابع يضيف ما يصل إلى 82-1 = 81 ، أو
• 2 إلى مجموعة من الطوابع يضيف ما يصل إلى 82-2 = 80 ، أو
• 7 إلى مجموعة من الطوابع يضيف ما يصل إلى 82-7 = 75 ، أو
• 12 إلى مجموعة من الطوابع يضيف ما يصل إلى 82-12 = 70 ، أو
• 50 إلى مجموعة من الطوابع إضافة ما يصل إلى 82-50 = 32.

هذه هي الطرق الوحيدة الممكنة التي يمكن تشكيل 82. من بين جميع هذه الاحتمالات الخمسة ، سيكون لدى واحد (أو ربما أكثر من واحد) الحد الأدنى لعدد الطوابع. إذا كان هذا الحد الأدنى هو> 5 ، فلا يمكن تمثيل 82 مع الطوابع.

لاحظ أيضًا أنه إذا كان من الممكن تمثيل الرقم ، فيجب عليك تسجيل الحد الأدنى لعدد الطوابع اللازمة لذلك بحيث يمكن استخدام الحسابات للأرقام الأعلى.

هذا ، زائد إجابة ستيف جيسوب, ، نأمل أن تحصل على عقلك على المسار الصحيح لحل البرمجة الديناميكية ... إذا كنت لا تزال متعثرًا ، فأخبرني بذلك.

Answer 3

بدلاً من حساب مبالغ جميع المجموعات الممكنة من الطوابع (ربما عن طريق العودية) ، فكر في كل ما هو ممكن مسائل حسابية, ، وتوصل إلى أصغر عدد من الطوابع لإنتاج كل مبلغ. هناك الكثير من مجموعات الطوابع ، ولكن عدد أقل بكثير من المبالغ المتميزة.

في المثال الذي قدمته في تعليق ، تتناسب 10 طوابع على مظروف ، ولا يوجد أي ختم بقيمة أكبر من 100. n^10 مجموعات من الطوابع ، حيث n هو عدد الطوابع المتاحة. لكن أكبر مبلغ ممكن من 10 طوابع هو 1000 فقط. قم بإنشاء صفيف يصل إلى 1001 ، ومحاولة التفكير في طريقة فعالة للعمل ، لجميع هذه القيم معًا ، أقل عدد من الطوابع المطلوبة لصنع كل واحدة. إجابتك هي أقل فهرس يتطلب 11 (أو أكثر) طوابع ، ويمكنك تحديد كل ختم في 11 ، أيضًا.

"كفاءة" في هذه الحالة يعني أساسًا ، "تجنب تكرار أي عمل لا تضطر إليه". لذا فأنت تريد إعادة استخدام النتائج المتوسطة قدر الإمكان.

إذا لم يكن هذا كافيًا من تلميح ، فأنا مخطئ في هذا النهج (في هذه الحالة آسف ، لم أحل المشكلة بنفسي قبل الإجابة) أو (ب) تحديث إلى أي مدى على هذا النحو.

Answer 4

ربما يكون من غير المفيد بعض الشيء إعطاء "تلميحات" حول حل DP عندما يكون هناك تكهنات بوجود واحد. لذا ، هنا يتم تشغيل رمز Perl القابل للتشغيل الذي ينفذ خوارزمية DP الفعلية:

#!/usr/bin/perl
my ($n, @stamps) = @ARGV;
my @_solved;        # Will grow as necessary

# How many stamps are needed to represent a value of $v cents?
sub solve($) {
    my ($v) = @_;
    my $min = $n + 1;

    return 0 if $v == 0;

    foreach (@stamps) {
        if ($v >= $_) {
            my $try = $_solved[$v - $_] + 1;
            $min = $try if $try < $min;
        }
    }

    $_solved[$v] = $min;
    return $min;
}

my $max = (sort { $a <=> $b } @stamps)[-1];

# Main loop
for (my $i = 0; $i <= $max * $n; ++$i) {
    my $ans = solve($i);
    if ($ans > $n) {
        print "$i cannot be represented with <= $n stamps of values " . join(", ", @stamps) . ".\n";
        last;
    }
}

عادة solve() سوف تتطلب مكالمة متكررة ، ولكن لأننا نحاول دائمًا القيم بالترتيب 0 ، 1 ، 2 ، 3 ... يمكننا فقط استخدام @_solved صفيف مباشرة للحصول على إجابة لأحجام المشكلات الأصغر.

يستغرق هذا 93 مللي ثانية على جهاز الكمبيوتر الخاص بي لحل حالة أحجام الطوابع 1 و 4 و 12 و 21 وحجم الظرف 1000. (الجواب هو 20967.) ستكون اللغة المترجمة أسرع.

Answer 5

        import java.util.ArrayList;
        import java.util.List;
        /**
         * 
         * @author Anandh
         *
         */
        public class MinimumStamp {

            /**
             * @param args
             */
            public static void main(String[] args) {
                // TODO Auto-generated method stub
                int stamps[]={90,30,24,15,12,10,5,3,2,1};
                int stampAmount = 70;
                List<Integer> stampList = minimumStamp(stamps, stampAmount);
                System.out.println("Minimum no.of stamps required-->"+stampList.size());    
                System.out.println("Stamp List-->"+minimumStamp(stamps, stampAmount));  
            }

            public static List<Integer> minimumStamp(int[] stamps, int totalStampAmount){
                List<Integer> stampList =  new ArrayList<Integer>();
                int sumOfStamps = 0;
                int remainingStampAmount = 0;
                for (int currentStampAmount : stamps) {
                    remainingStampAmount = totalStampAmount-sumOfStamps;
                    if(remainingStampAmount%currentStampAmount == 0){
                        int howMany = remainingStampAmount / currentStampAmount;
                        while(howMany>0){
                            stampList.add(currentStampAmount);
                            howMany--;
                        }
                        break;
                    }else if(totalStampAmount == (sumOfStamps+currentStampAmount)){
                        stampList.add(currentStampAmount);
                        break;
                    }else if(totalStampAmount > (sumOfStamps+currentStampAmount) ){
                        int howMany = remainingStampAmount / currentStampAmount;
                        if(howMany>0){
                            while(howMany>0){
                                stampList.add(currentStampAmount);
                                sumOfStamps += currentStampAmount;
                                howMany--;
                            }
                        }else{
                            stampList.add(currentStampAmount);
                            sumOfStamps += currentStampAmount;
                        }
                    }
                }
                return stampList;
            }
        }