كيف تحسب الحد الأدنى من النفايات عند خياطة أنابيب

Question

لدي مشكلة رياضية إلى حد ما أحتاج إلى حلها:

المهمة هي قطع عدد محدد مسبقا من الأنابيب خارج أنابيب طول ثابتة مع الحد الأدنى من مادة النفايات.

لذلك دعونا نقول أنني أرغب في خفض 10 1M أنابيب و 20 2 أنابيب خارج الأنابيب بطول موحدة 6M.

لست متأكدا مما تبدو عليه خوارزمية لهذا النوع من المشكلات؟

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

أولا لست متأكدا مما إذا كانت هناك طرق أخرى وأفضل لمهاجمة المشكلة.

ثانيا، لم أجد حلا كيف يمكنني إنشاء مثل هذه قائمة الاختلافات.

أي مساعدة يحظى بتقدير كبير، وذلك بفضل!

Answer 1

أعتقد أنك تصف مشكلة مخزون. وبعد يمكن العثور على بعض المعلومات الإضافية هنا.

Answer 2

هذا هو المعروف باسم خفض الأسهم مشكلة. يحتوي Wikipedia على عدد من المراجع التي قد تساعدك في العثور على أدلة على خوارزمية تعمل.