C++での棚のフィッティングの問題

この問題では、壁の長さW、棚のサイズn、およびmを示す3つの整数値W、n、mが与えられます。私たちのタスクは、フィッティングシェルフの問題を解決するプログラムを作成するです。 。

棚板を取り付けた後に残るスペースが最小限になるように、棚板を取り付ける方法を見つける必要があります。解決中の二次的な制約は製造コストです。棚が大きいほど費用効果が高いため、優先順位を付ける必要があります。

出力は次の形式である必要があります

nサイズの棚の数残りのmサイズの棚の数

問題を理解するために例を見てみましょう

Input: W = 12, n = 5, m = 3
Output: 0 4 0

説明

ここでは、壁に正確に4、3サイズの棚を取り付けることができます。

これにより、全長=4 * 3 =12

そのため、取り付け後に壁に長さが残っていません。

ソリューションアプローチ

この問題の簡単な解決策は、壁に取り付けられた棚の可能な組み合わせをそれぞれチェックし、壁のスペースの長さを最小化または排除するものを見つけることによるブルートフォースアプローチを使用することです。二次的なタスクでは、より大きな長さの拳をフィッティングすることから始めます。これにより、より大きなものが優先されます。どの組み合わせが最小の結果をもたらし、最適なソリューションのために可能な最大のラージシェルフを提供するかを確認します。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;

void solveFittingShelves(int wall, int m, int n){

   int numM = 0, numN = 0, minSpaceLeft = wall;
   int p = wall/m, q = 0, rem = wall%m;
   numM = p;
   numN = q;
   minSpaceLeft = rem;
   while (wall >= n) {
      q += 1;
      wall = wall - n;
      p = wall / m;
      rem = wall % m;
      if (rem <= minSpaceLeft) {
         numM = p;
         numN = q;
         minSpaceLeft = rem;
      }
   }
   cout<<numM<<" "<<numN<<" "<<minSpaceLeft<<endl;
}

int main(){
   int W = 29, m = 3, n = 9;
   cout<<"Length of wall : "<<W<<endl;
   cout<<"Length of shelves : "<<m<<"\t"<<n<<endl;
   cout<<"Optimal Shelves fitting : ";
   solveFittingShelves(W, m, n);
   return 0;
}

出力

Length of wall : 29
Length of shelves : 3 9
Optimal Shelves fitting : 0 3 2