組み合わせのプログラム

質問

組み合わせのプログラムを考えています。
例として tray[0]=1000, tray[1]=500, tray[2]=300 があるとします。
各配列の値を使って、その合計値が例えば「1000 以下」と言う条件に当てはまる組み合わせは 1000, 800(500+300), 500, 300, (0) です（各配列の値は１回だけ使用可能とします）。
１つの tray に対して、それを「足すか」「足さないか」の２通りが考えれるので、全体で2^n個(trayの数をnとする)の組み合わせを調べれば良いと思っています(これは間違っているのかな?!)
プログラムのイメージは以下のような感じです。
int sum,x;
(ここは x を使って if か for を使った足すか足さないかの条件ではないか!?){
sum=0;
for(int i=0;i<n;i++){

sum+=tray[i]*x;//ここでさきほどの x を使うのではないか、x に 0 or 1 が入ってくるイメージです
if(指定した数字(条件)>=sum) System.out.print("ここで組み合わせの出力");
}
}
初歩的な質問でお恥ずかしいです。
意味的に、かなりはしょった部分があるので、言いたい意味が分からないなど、ご質問がある方はご遠慮なくして下さい。
色々頑張ってみたのですが無理でした、もしご解答いただける方がいればすごく助かります。
宜しくお願いします。

回答No.3

BLUEPIXY · ベストアンサー

概ね、質問者の方針にしたがったサンプル
//--------------------------------------------
public class Sample {
public static void main(String[] args) {
int tray[] = { 1000, 500, 300 };
/* ３つから「足すか」「足さないか」は、
000
001
010
011
100
101
110
111
で表せる、従って、各trayがその組み合わせに含まれるかどうかは、
ビットがあるかどうかを調べれば良い
*/

for(int i=0;i<8;i++){
int sum=0;
if(0 != (i & 4)) sum+=tray[2];
if(0 != (i & 2)) sum+=tray[1];
if(0 != (i & 1)) sum+=tray[0];
if(sum<=1000)
System.out.println(sum);
}
}
}

お礼

ご解答ありがとうございます。本日自分なりに頑張って、一応やろうとしていたことは実現できました。
ただBLUEPIXY様からお教えいただいたプログラムと比べると、ものすごく効率が悪いと思います・・・。
以下のような感じです(例によって変数の宣言や意味ははっしょています)。
for(int k=0;k<count;k++) count2*=2;
for(int i=0;i<count;i++){
a=1;
b=0;
if(i!=0){
for(int j=0;j<i;j++) a*=2;
}
for(int k=0;k<count2;k++){
if(b!=a){
x[k][i]=0;
b++;
c=0;
}
else{
x[k][i]=1;
c++;
if(c==a) b=0;
}
}
}
なんと２次元配列を使ってビットがあるかどうかを探していました。
if(0 != (i & 4)) ←このような手法があるとは知りませんでした、お恥ずかしいです。
すごく参考になりました、よく意味を理解した上でこの手法を使わせていただきたいと思います。
またご縁がございましたら宜しくお願いします。

回答No.2

ngsvx

#1です。

聞き方が悪かったですか？

１、２、３からの選択という意味ではありません。

補足要求をして欲しい質問が３つあったのです。

回答No.1

ngsvx

疑問点です。

１．結局何を聞きたいのかがよくわかりません。
２．組み合わせは、２つだけでいいのでしょうか
３．条件に当てはまるものを全て出力するのかどうか

補足

「３．条件に当てはまるものを全て出力する」でお願いします。
言葉足らずで本当に申し訳ありません。