すべての組み合わせの列挙

Question

商品の情報をファイルから入手し、入力された予算に応じて買うことのできる全ての組み合わせを列挙する問題です。お助けいただけると幸いです。書いたコード貼っときます。()
例)F1.txt(name price amount /商品は10個と確定しています。)
Apple 1 20
Banana 4 25
Peach 4 34
Grape 4 3
Strawberry 2 40
Blueberry 3 9
Rice 10 2
Egg 1 22
Pen 6 10
Note 1 19

#include <stdio.h>
#include <float.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)

typedef struct{
   char name[30];
   float price;
   int amount;
}Data;

float budget;

void input(FILE* fi, Data* data) {
   rep(i,10) {
   	fscanf(fi,"%s %f %d", (data+i)->name, &(data+i)->price, &(data+i)->amount);
   }
}

int check(Data* data) {
   int f = 0;
   rep(i,10){
   	if(budget >= (data+i)->price) f++;
   }
   if(f==0) printf("you don't have enough money:'(\n");
   return f;
}


int count = 0;
//the number of all possible combinations
void pick(Data* data, int index, int maxindex, float price) {
   if(maxindex <= index) return;
   float newprice = price + (data+index)->price;
   if(newprice <= budget){ 
   	count++;
   	pick(data, index+1, maxindex, newprice);
   }
   pick(data, index+1, maxindex, price);
   		
}

int main(){
   Data p[10];
   Data *q = &p;
   char ni[10] ="F1.txt";
   FILE *fi;
   fi = fopen(ni,"r");
   printf("insert your budget!!\n");
   scanf("%f", &budget);
   input(fi, q);
   int C = check(q);
   if(C == 0) return 0;
   pick(q, 1, 9, 0);
   printf("%d", count);
   /*rep(i,10) {
   	printf("%s %f %d\n", (q+i)->name, (q+i)->price, (q+i)->amount);
   }*/
   
   return 0;
   
}



   

Answer 1

いわゆるナップサック問題ですね

ナップサック問題は大体条件があるので、
枝刈りという、その条件に合致しないパターンであれば探索を打ち切る仕組みが入りますが、
この例だとすべて列挙なので枝刈りも必要ないです

ちょっと修正して、１が3つあるとき、最大2円で6が返ってくるのを確認しました

#include <stdio.h>
struct Data{
  float price;
};

int pick(Data *data, int index, int maxindex, float price, float maxprice){
  int count = 0;
  if (maxindex <= index) return 0;
  float newprice = price + data[index].price;
  if (newprice <= maxprice){
    (count)++;
    // indexの商品を追加して次の工程に
    count += pick(data, index + 1, maxindex, newprice, maxprice);
  }
  // indexの商品を追加せずに次の工程に
  count += pick(data, index + 1, maxindex, price, maxprice);
  return count;
}

int main(){
  Data d[] = {{1}, {1}, {1}};
  
  int count = pick(d, 0, 3, 0, 2);
  printf("%d", count);
}

Comments

[gekko]

ありがとうございます!参考にさせていただきます!

[gekko]

何通りかはは出すことができました。問題は実際に全ての組み合わせをターミナルに表示しなければならないのでその部分をどうしたらいいか実装してみます。!

[kazuma-s]

何通りか出すことができるそのコードと、10個のデータを書いた F1.txt を質問に追加してもらうと、私の回答を示せます。あと、何通りか出すことができた時に使った予算の値もお願いします。

[gekko]

気づいたのですが1とかで試してみると1としかかえってこなくて、本当は価格が1のものが3つあるので3と返したいのですが。。もうすこし変えてみます！

[gekko]

あと個数も入れなくちゃいけなくてもしお助けいただけるとうれしいです

Answer 2

質問のコードの main で、Data *q = &p; の行で警告が出ませんか？
使用しているコンパイラは何ですか？

#include <stdio.h>

typedef struct {
    char name[30];
    float price;
    int amount;
} Data;

float budget;

void input(FILE *fi, Data *data)
{
	for (int i = 0; i < 10; i++)
        fscanf(fi,"%s %f %d", data[i].name, &data[i].price, &data[i].amount);
}

int check(const Data *data)
{
	for (int i = 0; i < 10; i++)
        if (budget >= data[i].price) return 1;
    printf("you don't have enough money:'(\n");
    return 0;
}

void search(const Data *data, int i, float money, int *count)
{
	if (i == 10) {
		const char *sep = "";
		for (int j = 0; j < 10; j++)
			if (count[j] > 0) {
				printf("%s%s %d", sep, data[j].name, count[j]); 
				sep = ", ";
			}
		putchar('\n');
	}
	else
		for (count[i] = 0; count[i] <= data[i].amount; count[i]++) {
			float cost = data[i].price * count[i];
			if (cost > money) return;
			search(data, i + 1, money - cost, count);
		}
}

int main(void)
{
    Data data[10];
	int count[10];
    FILE *fi = fopen("F1.txt", "r");
	if (!fi) return 1;
    printf("insert your budget!!\n");
    scanf("%f", &budget);
    input(fi, data);
	fclose(fi);
    if (check(data)) search(data, 0, budget, count);
    return 0;
}

このように書いてみましたが、これは期待するものでしょうか？

Comments

[gekko]

ありがとうございます！　はい！！これがしたかったんです。ほんとにあろがとうございます！！

[kazuma-s]

質問のコードの main で、Data *q = &p; の行で警告が出ませんか？
使用しているコンパイラは何ですか？