このディレクトリの索引
http://pc12.2ch.net/test/read.cgi/tech/1258158172/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,_許容最大重量,_詰めることのできる最高合計金額) :-
  データファイルの読み出し(_ファイル名,N,_価格ならび,_重さならび),
  findall(M,for(1,M,N),_1からNまで),
  findmax(_合計価格,詰め物の作成(N,_1からNまで,_許容最大重量,_重さならび,_価格ならび,_合計価格),_詰めることのできる最高合計金額).

データファイルの読み出し(_ファイル名,N,_重さならび,_価格ならび) :-
  see(_ファイル名),get_integer(N),get_integers(L1),seen,
  length(L2,N),length(L3,N),
  append(_重さならび,_価格ならび,L1),!.

詰め物の作成(N,_1からNまで,_許容最大重量,_重さならび,_価格ならび,_合計価格) :-
  for(1,M,N),
  組合せ(_1からNまで,M,L),
  findsum(Wi,(member(A,L),list_nth(A,_重さならび,Wi)),_合計重量),
  _合計重量 =< _許容最大重量,
  findsum(Pi,(member(A,L),list_nth(A,_価格ならび,Pi)),_合計金額).

get_integers(L) :-
  findall(I,(get_line(Line),(Line=end_of_file,!,fail;atom_to_term(Line,I,_))),L),!.