このディレクトリの索引

# 出典 :: C/C++の宿題片付けます 132代目 #456 # [1] 授業単元: C++ # [2] 問題文(含コード&リンク): # http://ime.nu/kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/10195.txt # # 今回はナップサック問題について考えプログラムを作成する。N個の荷物があって、個々の荷物の重さをWi、値段をPiとする。但しiは1からNの整数を意味する。 # 袋には最大Wの重さまで入れられるとすると、最大でいくら分を入れることができるか?という問題。 # データファイルは、始めの一行に荷物の個数Nが書かれており、次に重さが整数でN行分書かれている。その次の行からN行分、それぞれの荷物の価値が書かれているとする。 # 下のデータファイルの場合は、3個の荷物があり、重みは10、20、13、で # それぞれの値段は23、23、10という状況を表す。 # ------------------- # 3 # 10 # 20 # 13 # 23 # 23 # 10 # ------------------- # 荷物の重みと値段はともに、1から100までの乱数で与えることとする。 # void_write_data_file(char*file,intN)という関数を呼ぶとN個分のデータを乱数で生成し、文字列変数fileに入っている # ファイル名のファイルを開き、そこにデータを記録する。void_read_data_file(char*file)という関数を呼ぶと、文字列変数fileによって名前が指定されたファイルを開き、大域変数の荷物の重み配列W[]と値段配列[]\\\\\にデータを入力する。 ナップサック問題(_ファイル名,_許容最大重量,_詰めることのできる最高合計金額) :- 'N個の荷物があって、個々の荷物の重さをWi、値段をPiとする。但しiは1からNの整数を意味する。 袋には最大Wの重さまで入れられるとすると、最大でいくら分を入れることができるか? データファイルは、始めの一行に荷物の個数Nが書かれており、次に重さが整数でN行分書かれている。 その次の行からN行分、それぞれの荷物の価値が書かれているとする。'(_ファイル名,_許容最大重量,_詰めることのできる最高合計金額). 'N個の荷物があって、個々の荷物の重さをWi、値段をPiとする。但しiは1からNの整数を意味する。 袋には最大Wの重さまで入れられるとすると、最大でいくら分を入れることができるか? データファイルは、始めの一行に荷物の個数Nが書かれており、次に重さが整数でN行分書かれている。 その次の行からN行分、それぞれの荷物の価値が書かれているとする。'(_ファイル名,N,_許容最大重量,_詰めることのできる最高合計金額) :- 'データファイルは、始めの一行に荷物の個数Nが書かれており、次に重さが整数でN行分書かれている。 その次の行からN行分、それぞれの荷物の価値が書かれているとする。'(_ファイル名,N,_重さならび,_価格ならび), 'N個の荷物があって、個々の荷物の重さをWi、値段をPiとする。但しiは1からNの整数を意味する。 袋には最大Wの重さまで入れられるとすると、最大でいくら分を入れることができるか?'(N,_許容最大重量,_重さならび,_価格ならび,_詰めることができる最高合計金額). 'N個の荷物があって、個々の荷物の重さをWi、値段をPiとする。但しiは1からNの整数を意味する。 袋には最大Wの重さまで入れられるとすると、最大でいくら分を入れることができるか?'(N,_許容最大重量,_重さならび,_価格ならび,_詰めることができる最高合計金額) :- findall(M,between(1,N,M),_1からNまで), findmax(_合計価格,詰め物の作成(N,_1からNまで,_許容最大重量,_重さならび,_価格ならび,_合計価格),_詰めることのできる最高合計金額). 'データファイルは、始めの一行に荷物の個数Nが書かれており、次に重さが整数でN行分書かれている。 その次の行からN行分、それぞれの荷物の価値が書かれているとする。'(_ファイル名,N,_重さならび,_価格ならび) :- 'データファイルは、始めの一行に荷物の個数Nが書かれており、'(_ファイル名,N), '次に重さが整数でN行分書かれている。'(N,_重さならび), 'その次の行からN行分、それぞれの荷物の価値が書かれているとする。'(N,_価格ならび). 'データファイルは、始めの一行に荷物の個数Nが書かれており、'(_ファイル名,N) :- see(_ファイル名), 整数を得る(N). 整数を得る(_整数) :- 行入力(_行), atom_number(_行,_整数). 行入力(_行) :- read_line_to_codes(current_input,_文字コードならび), atom_codes(_行,_文字コードならび). '次に重さが整数でN行分書かれている。'(N,_重さならび) :- findall(_重さ,( 重さを読みだす(N,_重さ)),_重さならび). 重さを読みだす(N,_重さ) :- between(1,N,_), 整数を得る(_重さ). 'その次の行からN行分、それぞれの荷物の価値が書かれているとする。'(N,_価格ならび) :- findall(_価格,( 価格を読みだす(N,_価格)),_価格ならび), seen. 価格を読みだす(N,_価格) :- between(1,N,_), 整数を得る(_価格). 詰め物の作成(N,_1からNまで,_許容最大重量,_重さならび,_価格ならび,_合計価格) :- '1からNまでの全ての部分組合せを得る'(N,_1からNまで,L), 許容最大重量以下の合計重量の時の合計金額(L,_許容最大重量,_重さならび,_価格ならび,_合計金額). '1からNまでの全ての部分組合せを得る'(N,_1からNまで,L) :- between(1,N,M), 組合せ(_1からNまで,M,L). 許容最大重量以下の合計重量の時の合計金額(L,_許容最大重量,_重さならび,_価格ならび,_合計金額) :- 許容最大重量以下の合計重量の時の(L,_許容最大重量,_重さならび), 合計金額(L,_価格ならび,_合計金額). 許容最大重量以下の合計重量の時の(L,_許容最大重量,_重さならび) :- findsum(Wi,( 位置情報から重量を得る(L,_重さならび,Wi)),_合計重量), _合計重量 =< _許容最大重量. 位置情報から重量を得る(L,_重さならび,Wi) :- member(_nth1,L), nth1(_nth1,_重さならび,Wi). 合計金額(L,_価格ならび,_合計金額) :- findsum(Pi,( 位置情報から価格を得る(L,_価格ならび,Pi)),_合計金額). 位置情報から価格を得る(L,_価格ならび,Pi) :- member(_nth1,L), nth1(_nth1,_価格ならび,Pi). findmax(_射影項,_目標,_最大値) :- findall(_射影項,_目標,_射影項ならび), max_list(_射影項,_最大値). findsum(_射影項,_目標,_合計) :- findall(_射影項,_目標,_射影項ならび), sum_list(_射影項,_合計). 組合せ(X,1,[A]) :- member(A,X). 組合せ([A|Y],N,[A|X]) :- N > 1, succ(M,N), 組合せ(Y,M,X). 組合せ([_|Y],N,A) :- N > 1, 組合せ(Y,N,A).