C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

ビンパッキングアルゴリズムを実装するためのC++プログラム


ビンパッキング問題は、特殊なタイプのカッティングストック問題です。ビンパッキング問題では、使用されるビンの数を最小限に抑える方法で、異なるボリュームのオブジェクトを有限数のコンテナーまたは各ボリュームVのビンにパックする必要があります。計算の複雑さの理論では、これはNP困難な組み合わせの問題です。

ビンの数が1に制限され、各アイテムがボリュームと値の両方で特徴付けられる場合、ビンに収まるアイテムの値を最大化する問題はナップサック問題と呼ばれます。

アルゴリズム

Begin
   Binpacking(pointer, size, no of sets)
   Declare bincount, m, i
   Initialize bincount = 1, m=size
   For i = 0 to number of sets
   if (m - *(a + i) > 0) do
      m = m - *(a + i)
      Continue
   Else
      Increase bincount
      m = size;
      Decrement i
      Print number of bins required
End

サンプルコード

#include<iostream>
using namespace std;
void binPacking(int *a, int size, int n) {
   int binCount = 1;
   int m = size;
   for (int i = 0; i < n; i++) {
      if (m - *(a + i) > 0) {
         m -= *(a + i);
         continue;
      } else {
         binCount++;
         m = size;
         i--;
      }
   }
   cout << "Number of bins required: " << binCount;
}
int main(int argc, char **argv) {
   cout << "Enter the number of items in Set: ";
   int n;
   cin >> n;
   cout << "Enter " << n << " items:";
   int a[n];
   for (int i = 0; i < n; i++)
      cin >> a[i];
   cout << "Enter the bin size: ";
   int size;
   cin >> size;
   binPacking(a, size, n);
}

出力

Enter the number of items in Set: 3
Enter 3 items:4
6
7
Enter the bin size: 26
Number of bins required: 1

  1. Kadaneのアルゴリズムを実装するためのC++プログラム

    Kadaneのアルゴリズムは、整数の配列から最大のサブ配列の合計を見つけるために使用されます。ここでは、このアルゴリズムを実装するためのC++プログラムについて説明します。 アルゴリズム Begin Function kadanes(int array[], int length):    Initialize    highestMax = 0    currentElementMax = 0    for i = 0 to length-1       currentElement

  2. ヴィジュネル暗号を実装するためのC++プログラム

    Vigenere Cipherは、アルファベットのテキストを暗号化する一種の多表式置換方法です。 この方法での暗号化と復号化には、AからZまでのアルファベットが26行で書き込まれるVigenereCipherTableが使用されます。 暗号化 キー: ようこそ メッセージ: Thisistutorialspoint ここでは、指定されたキーの長さが元のメッセージの長さと等しくなるまで、そのキーを繰り返してキーを取得する必要があります。 暗号化の場合は、メッセージの最初の文字とキー(TとW)を取得します。V行とW列が一致するVigenere Cipher Tableのアルファベ