質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

2回答

942閲覧

(緊急)ソースコードの変数の意味が分からない

Exige_S

総合スコア0

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2022/12/13 22:34

編集2022/12/15 11:39

前提

-変数bnの意味が分かりません
自力で解決しようとしたところ、訳が分からなくなってしまって手に負えなくなってしまいました…
研究の締め切りが迫っているので、お願いします。

実現したいこと

  • 卒業研究での「ビンパッキング問題に用いるアルゴリズムの比較」のために最近傍探索を用いたサブルーチンを実装したい

実装するために、まずサブルーチンが戻す変数bnの意味を知る必要がある

該当のソースコード

C++

1#include <iostream> 2#include <algorithm> 3#include <vector> 4#include <list> 5#include <xlocale> 6#include <cstdlib> 7 8const int BIN_SIZE = 100; //ビンの大きさ 9const int MAX_CAP = 70; //荷物の最大の大きさ 10const int MIN_CAP = 10; //荷物の最小の大きさ 11const int BIN_NUM = 1000; //ビンの本数 12 13using namespace std; 14 15 16 17int rand_generate(int c[], int n, unsigned int seed = 0) 18{ 19 srand(seed); 20 int sum = 0; 21 for (int i = 0; i < n; i++) 22 { 23 int r = rand() % (MAX_CAP - MIN_CAP + 1) + MIN_CAP; 24 c[i] = r; 25 sum += r; 26 } 27 return sum; 28} 29 30void disp_array(const int a[], int n) 31{ 32 for (int i = 0; i < n; i++) 33 { 34 cout << a[i] << ", "; 35 } 36 cout << endl; 37} 38 39void clear_bin(int bs[], int n) 40{ 41 for (int b = 0; b < n; b++) 42 bs[b] = BIN_SIZE; 43} 44 45int check_packing(const int bin[], const int c[], int c_num) 46{ 47 int b_space[BIN_NUM]; //ビンの空き容量 48 clear_bin(b_space, BIN_NUM); 49 50 for (int i = 0; i < c_num; i++) //品物 51 { 52 b_space[bin[i]] -= c[i]; 53 if (b_space[bin[i]] < 0) 54 { 55 cout << "ビンパッキングが異常です\n"; 56 return 1; 57 } 58 } 59 return 0; 60} 61 62//first_fitアルゴリズム。ビンの列の先頭から調べ、入れることができたら入れる 63int first_fit(int bin[], const int c[], int n) 64{ 65 int b_space[BIN_NUM]; //ビンの空き容量 66 clear_bin(b_space, BIN_NUM); 67 68 for (int i = 0; i < n; i++) //品物 69 { 70 int bc = c[i]; //品物の容量 71 for (int b = 0; ; b++) 72 { 73 if (b_space[b] > bc) //空き容量より小さければ 74 { 75 b_space[b] -= bc; 76 bin[i] = b; 77 break; 78 } 79 } 80 } 81 82 check_packing(bin, c, n); 83 int bn; 84 for (bn = 0; b_space[bn] < BIN_SIZE; bn++); 85 return bn; 86} 87 88void disp_packing(const int bin[], int bi_num, const int c[], int c_num) 89{ 90 for (int b = 0; b < bi_num; b++) 91 { 92 for (int i = 0; i < c_num; i++) 93 { 94 if (bin[i] == b) 95 cout << c[i] << "(" << i << ")" << ", "; 96 } 97 cout << endl; 98 } 99} 100 101int is_opt(int sum, int bin_num) 102{ 103 div_t qr = div(sum, BIN_SIZE); 104 return bin_num == (qr.rem ? qr.quot + 1: qr.quot); 105} 106 107int first_fit_decreasing(const int c[], int n) 108{ 109 int* temp = new int[n]; 110 int* bi = new int[n]; 111 for (int i = 0; i < n; i++) 112 temp[i] = c[i]; 113 114 sort(temp, temp + n, [](int x, int y) { return x > y;}) ; //逆順にソートしてから 115 116 int ret = first_fit(bi, temp, n); //first_fitアルゴリズムをかける 117 delete[] temp; 118 delete[] bi; 119 return ret; 120} 121 122//ランダムにビンに入れる 123int rand_pack(int bin[], int b_space[], const int c[], int c_num, unsigned int seed = 0) 124{ 125 clear_bin(b_space, BIN_NUM); 126 srand(seed); 127 int max_b = -1; 128 for (int i = 0; i < c_num; i++) 129 { 130 int ci = c[i]; 131 for (int r = rand() % c_num; ; r = rand() % c_num) 132 { 133 if (ci <= b_space[r]) //ビンに入るなら入れる 134 { 135 if (max_b < r) 136 max_b = r; 137 bin[i] = r; 138 b_space[r] -= ci; 139 break; 140 } 141 } 142 } 143 return max_b + 1; 144} 145 146//可能な限り先頭に移動させる 147int local_seach1(int bin[], const int c[], int c_num) 148{ 149 int b_space[BIN_NUM]; //ビンの空き容量 150 int bn = rand_pack(bin, b_space, c, c_num); 151 // disp_packing(bi, bn, c, c_num); 152 // disp_array(b_space, bn); 153 154 int flag = 1; 155 for (int it = 0; flag; it++) 156 { 157 flag = 0; 158 for (int i = 0; i < c_num; i++) 159 { 160 int bi = bin[i]; //iのビン番号 161 int ci = c[i]; //iの容量 162 for (int b = 0; b < bi; b++) //iより前のビンをスキャン 163 { 164 if (b_space[b] >= ci) //前に移動できる 165 { 166 b_space[bi] += ci; //移動 167 b_space[b] -= ci; 168 bin[i] = b; //j番目に詰め替える 169 flag = 1; 170 break; 171 } 172 173 } 174 } 175 } 176 check_packing(bin, c, c_num); 177 for (bn = 0; b_space[bn] < BIN_SIZE; bn++); 178 return bn; 179} 180 181//可能な限り先頭に移動させる(2近傍) 182int local_seach2(int bin[], const int c[], int c_num) 183{ 184 int b_space[BIN_NUM]; //ビンの空き容量 185 int bn = rand_pack(bin, b_space, c, c_num); 186 187 int flag = 1; 188 for (int it = 0; flag; it++) 189 { 190 flag = 0; 191 for (int i = 0; i < c_num; i++) 192 { 193 int bi = bin[i]; //ビン番号 194 int ci = c[i]; //biの容量 195 196 int b; 197 for (b = 0; b < bi; b++) //biより前のビンをスキャン 198 { 199 if (b_space[b] >= ci) //前に移動できる 200 { 201 b_space[bi] += ci; //移動 202 b_space[b] -= ci; 203 bin[i] = b; //j番目に詰め替える 204 flag = 1; 205 break; 206 } 207 } 208 if (b == bi) //上で改善できなかった場合、 209 { 210 for (int j = 0; j < c_num; j++) 211 { 212 int bj = bin[j]; //jが入っているビン 213 if (bj < bi) //jが前のビンならば 214 { 215 int cj = c[j]; //jの容量 216 if (ci > cj) 217 { 218 int w = b_space[bj] + cj - ci; //jを取り除いてiを入れてみる 219 if (w >= 0) //変更可能 220 { 221 b_space[bj] = w; 222 b_space[bi] += ci - cj; 223 bin[i] = bj; 224 bin[j] = bi; 225 flag = 1; 226 break; 227 228 } 229 230 } 231 } 232 } 233 } 234 } 235 } 236 check_packing(bin, c, c_num); 237 for (bn = 0; b_space[bn] < BIN_SIZE; bn++); 238 return bn; 239} 240 241/*実装しようとした部分 242int nearest_neighbor_seach(int bin[], const int c[], int c_num) { 243 int b_space[BIN_NUM]; //ビンの空き容量 244 int bn = rand_pack(bin, b_space, c, c_num); 245 // disp_packing(bi, bn, c, c_num); 246 // disp_array(b_space, bn); 247 248 int flag = 1; 249 for (int it = 0; flag; it++) 250 { 251 flag = 0; 252 for (int i = 0; i < c_num; i++) 253 { 254 255 if (bin[i] > ci) 256 { 257 secondLargest = ci; 258 largest = bin[i]; 259 if (b_space[b] >= ci) //前に移動できる 260 { 261 b_space[bi] += ci; //移動 262 b_space[b] -= ci; 263 bin[i] = b; //j番目に詰め替える 264 flag = 1; 265 break; 266 } 267 } 268 269 else if (bin[i] > secondLargest && 270 bin[i] != c_num) 271 secondLargest = bin[i]; 272 } 273 } 274 check_packing(bin, c, c_num); 275 for (bn = 0; b_space[bn] < BIN_SIZE; bn++); 276 return bn; 277} 278*/ 279 280int main() 281{ 282 const int OBJ_NUM = 100; //品物の個数 283 int cap[OBJ_NUM]; // = { 50, 60, 50, 40, 40 }; //品物の重さ配列 284 int sum = rand_generate(cap, OBJ_NUM); //ランダムに重さ割り当て、その合計を戻す 285 286 cout << sum << endl; 287 disp_array(cap, OBJ_NUM); 288 289 int bin_index[OBJ_NUM]; //品物が入っているビン番号 290 291 int ff_bn = first_fit(bin_index, cap, OBJ_NUM); 292 cout << "first_fit : " << ff_bn << endl; 293 294 int ffd_bn = first_fit_decreasing(cap, OBJ_NUM); 295 cout << "first_fit減少列 : " << ffd_bn << endl; 296 297 int ls_bn = local_seach1(bin_index, cap, OBJ_NUM); 298 cout << "local_search1 : " << ls_bn << endl; //ローカルサーチ(1近傍) 299 300 ls_bn = local_seach2(bin_index, cap, OBJ_NUM); 301 cout << "local_search2 : " << ls_bn << endl; //ローカルサーチ(2近傍) 302 303 return 0; 304} 305 306

試したこと

ソースコードを読んでメモ帳にまとめて、理解しようと試みた
最近傍探索アルゴリズムのサブルーチンの実装を試みた

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

y_waiwai

2022/12/13 23:17

そのコードはなにをするもんなんでしょうか
Exige_S

2022/12/13 23:32

ビンパッキング問題の解決に用いるアルゴリズムの比較のためのコードみたいです… 実行時に各アルゴリズムごとのサブルーチンから値が戻ってきて、その戻ってきた値がモニターに表示されるっていうシロモノです 問題は、その戻ってくる値が一体何なのかがわからないんですね…
Zuishin

2022/12/14 00:01

自分で作ったソースでもないのに出典を示さないのはいかがなものか。 日本の法律では犯罪になります。
pig_vba

2022/12/14 00:12 編集

引用元明記もそうですが、正直なところ表題に(緊急)とかつけるのは推奨できません。知恵袋では確かに緊急枠みたいなのがあるらしいですが、そんなのがないteratailでは回答者からすれば「しらんがな。もっと早くから動いとけ」で終わる話なので。 まぁ、おそらくはラボの先輩の残したコードをパクッたってところでしょうから問題にはなりにくいでしょうが…
BeatStar

2022/12/15 01:26

んで、「緊急」と相手に急かしてまで強要しているのに自分は貰った答えにすら返信しないのはなんでしょうか?
Zuishin

2022/12/15 01:45

知恵袋では「至急」「急募」と書くとアプリでは特別扱いされるそうで、ご存知の通りこのサイトでも「至急」と書く人が多かったわけですが、「至急」が嫌われるということがわかって「緊急」と書く人が出てきました。 つまり「緊急」と書く人は、「至急」という言葉を避けつつ同じ意味のことを書きたいためにそう書いていると思われます。 NG ワードに登録されていないワードなら通るという判断じゃないでしょうか。 恐らく回答者を人間扱いしてないですね。
BeatStar

2022/12/15 01:55

@ Zuishinさん うわ…そういうことですか…。
guest

回答2

0

int b_space[BIN_NUM]; //ビンの空き容量 ・・・処理・・・ for (bn = 0; b_space[bn] < BIN_SIZE; bn++); return bn;

clear_bin関数よりb_space[x]の最大値はBIN_SIZEなので、
ここで返しているのはb_space[bn]=BIN_SIZEになる最初の番号、
すなわち何本ビンを消費したかを結果として返しています。ビンパッキング問題は「使用本数をどれだけ減らせるか」という問題であることを考えれば使用本数以外返す理由がないことは理解できると思います
使用しているのはbin[bn-1]までですが、配列は0から始まるため要件を満たすbn=使用本数となるわけです。

投稿2022/12/13 23:58

編集2022/12/14 00:00
pig_vba

総合スコア807

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

pig_vba

2022/12/15 02:39

ふむ。緊急の案件なのに丸一日放置できるんですねぇ…大変興味深い価値観です
guest

0

c

1for (bn = 0; b_space[bn] < BIN_SIZE; bn++); 2return bn;

bn=0から見ていって
b_space[bn] >= BIN_SIZEとなる最初のbnです

投稿2022/12/13 23:29

ozwk

総合スコア13512

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問