プログラマ専用SNS ミクプラ

容量CのバッグにN種類の商品（各々値段ｐ、容量ｃ）から複数個を選んで詰め込む。
その際詰め込む商品の合計金額が出来るだけ高くなる様に商品を選び、その内容を表示するプログラムを作成せよ。

＜実行結果例＞
Input Capacity C of the bag : 13
Input the number of kinds of goods : 4

Input the detailed information of each goods.

No. 1 c : 5
No. 1 p : 140

No. 2 c : 3
No. 2 p : 120

No. 3 c : 4
No. 3 p : 130

No. 4 c : 7
No. 4 p : 400

No. p
4 400
2 120
2 120
total 640

以上が実行例です。
現在の私のプログラムは下です。
#include<stdio.h>

int main(void)

{
int a,b,c,d；
int x;

printf("Input Capacity C of the bag : ");
scanf("%d",&a);

printf("Input the number of kinds of goods : ");
scanf("%d",&b);
printf("\n");

printf("Input the detailed information each goods.");
printf("\n");

for(x=1;x<=b;x++)
{
printf("No.%d c:",x);
scanf("%d",&c);

printf("No.%d p:",x);
scanf("%d",&d);
printf("\n");
}
}

以上が現在のプログラムです。
N種類の商品から合計金額が最も多くなるようバッグに詰め込むプログラムがわかりません。
どうやってバッグの大きさに合わせて、金額最大になるようにするのですか？
教えてください。

pok さんが書きました:容量CのバッグにN種類の商品（各々値段ｐ、容量ｃ）から複数個を選んで詰め込む。
その際詰め込む商品の合計金額が出来るだけ高くなる様に商品を選び、その内容を表示するプログラムを作成せよ。

単純に考えれば、
1.金額が高い順に商品を順番にバッグに詰めていく
2.入れようとしている商品を入れるとバッグの容量をオーバーするのであれば、それは諦めて次に高い商品を試してみる
3.最終的に一番安い商品まで試したら終了。この時点でバッグに入っているのが出来るだけ高い金額の商品を詰め合わせた結果

という流れでしょうか。

なので必要な処理としては、
・バッグの容量と各商品の情報を入力してもらう
・入力された商品を金額順にソートする(高い順にバッグに入れていくので)
・バッグに入れられる場合は入れた商品を保存しておく(最後に表示するので)

といったところでしょうか。

バッグの容量はint型変数一つでよいとは思いますが、
各商品には2つの情報(金額、容量)があるので、構造体にしたほうが扱いやすいと思います。
別々の配列で保存するとソートしたときに関連が崩れてしまいますし。

また、各商品がいくつあるのかは実際に実行したときに入力してもらうまでわかりません。
なので、入力を受けた後で動的に準備する必要があります。

そこでpokさんに確認なのですが、

・配列の使い方はわかりますか？
・構造体の使い方はわかりますか？
・動的な配列(ポインタ)確保の方法はわかりますか？
→入力してもらう個々の商品情報を記憶しておく配列とバッグに入っている商品一覧を記憶しておく配列が必要です
・ソートの方法は分かりますか？

pokさんがどこまで分かっているのか教えてください。

今のままだと複数の商品情報を保存する変数がないと思います。
あと、各変数がa,b,c,d,xとなっていますが、何に使われている変数が分からないので、
bag_capacityとかpriseとか分かりやすい名前にしたほうがバグを未然に防げると思います。
#あれ、商品の重さってaだっけ？bだっけ？となるとバグの元です

投稿後に実行結果例に疑問が沸きましたので教えてください。

pok さんが書きました: ＜実行結果例＞
Input Capacity C of the bag : 13
Input the number of kinds of goods : 4

Input the detailed information of each goods.

No. 1 c : 5
No. 1 p : 140

No. 2 c : 3
No. 2 p : 120

No. 3 c : 4
No. 3 p : 130

No. 4 c : 7
No. 4 p : 400

No. p
4 400
2 120
2 120
total 640

以上が実行例です。

実行例では以下の状態になっています。
バッグの容量：13
商品数：4

商品1：容量 5、価格 140
商品2：容量 3、価格 120
商品3：容量 4、価格 130
商品4：容量 7、価格 400

最終的な答え：商品4、商品2、商品2

てっきり商品は1つずつだと思っていましたが、同じ商品を複数入れてもOKということでしょうか。
とすると、私の書いた「高い順に詰め込んでいく」処理ではもっとも高い答えにはならないですね、すみません。
各商品は1個だと思い込んでいました。

所謂普通のナップサック問題ですね。
商品の内容を表示する順番の規則は決まっていますか？
pokさんが提示した出力例とは順番が違いますが、内容は同じです。

コード:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int c,p;
} goods_t;

typedef struct {
	int written;
	int p;
	int nextGoods;
} memo_t;

goods_t* goodsList;
memo_t* memo;

int tansaku(int now,int max,int rest) {
	int i;
	int result;
	int tempResult;
	int resultGoods;
	if(memo[rest*max+now].written)return memo[rest*max+now].p;
	result=0;
	resultGoods=-1;
	for(i=now;i<max;i++) {
		if(goodsList[i].c<=rest) {
			tempResult=goodsList[i].p;
			tempResult+=tansaku(i,max,rest-goodsList[i].c);
			if(tempResult>result) {
				result=tempResult;
				resultGoods=i;
			}
		}
	}
	memo[rest*max+now].written=1;
	memo[rest*max+now].p=result;
	memo[rest*max+now].nextGoods=resultGoods;
	return result;
}

int main(void)
{
	int a,b,c,d;
	int x;
	int result;
	int nowGoods,nowRest;

	printf("Input Capacity C of the bag : ");
	scanf("%d",&a);

	printf("Input the number of kinds of goods : ");
	scanf("%d",&b);
	printf("\n");

	goodsList=malloc(b*sizeof(goods_t));
	memo=calloc(a*(b+1),sizeof(memo_t));

	printf("Input the detailed information each goods.");
	printf("\n");
	printf("\n");

	for(x=1;x<=b;x++)
	{
		printf("No.%d c : ",x);
		scanf("%d",&c);

		printf("No.%d p : ",x);
		scanf("%d",&d);
		printf("\n");

		goodsList[x-1].c=c;
		goodsList[x-1].p=d;
	}

	result=tansaku(0,b,a);
	puts("No. p");
	for(nowGoods=memo[a*b].nextGoods,nowRest=a;
			nowGoods>=0;nowGoods=memo[nowRest*b+nowGoods].nextGoods) {
		nowRest-=goodsList[nowGoods].c;
		printf("%d %d\n",nowGoods+1,goodsList[nowGoods].p);
	}
	printf("total %d\n",result);

	free(goodsList);
	free(memo);

	return 0;
}

このプログラムの実行結果例です。

コード:

Input Capacity C of the bag : 13
Input the number of kinds of goods : 4

Input the detailed information each goods.

No.1 c : 5
No.1 p : 140

No.2 c : 3
No.2 p : 120

No.3 c : 4
No.3 p : 130

No.4 c : 7
No.4 p : 400

No. p
2 120
2 120
4 400
total 640

asdさんの方法は、貪欲法と呼ばれるものですね。
確信はありませんが、一般的に正しい結果を出力できないコーナーケースがあると思います。

最大値が同じものはすべて表示するようにしてみました。

コード:

#include <stdio.h>
#include <stdlib.h>

struct Goods { int capa, price, count; } *g;
int kind, total = -1, max = -1;

void proc(int bag, int n)
{
    if (n == 0) {
        int i, j, price = 0;
        for (i = 0; i < kind; i++) price += g[i].price * g[i].count;
        if (price == max) {
            printf("\nNo. p\n");
            for (i = 0; i < kind; i++)
                for (j = 0; j < g[i].count; j++)
                    printf("%d %d\n", i+1, g[i].price);
            printf("total %d\n", price);
        } else if (price > total) total = price;
    } else {
        int k = bag / g[--n].capa;
        for (g[n].count = 0; g[n].count <= k; g[n].count++, bag -= g[n].capa)
            proc(bag, n);
    }
}

int main(void)
{
    int i, bag;
    printf("Input Capacity C of the bag : "), scanf("%d", &bag);
    printf("Input the number of kinds of goods : "), scanf("%d", &kind);
    g = malloc(sizeof(struct Goods) * kind);
    printf("\nInput the detailed information each goods.\n");
    for (i = 0; i < kind; i++) {
        printf("\nNo.%d c : ", i+1), scanf("%d", &g[i].capa);
        printf("No.%d p : ", i+1), scanf("%d", &g[i].price);
    }
    proc(bag, kind);
    max = total;
    proc(bag, kind);
    free(g);
    return 0;
}

みけCAT さんが書きました: asdさんの方法は、貪欲法と呼ばれるものですね。
確信はありませんが、一般的に正しい結果を出力できないコーナーケースがあると思います。

その通りです。お恥ずかしい限りですorz
少なくとも今回の場合は価値の少ないものを複数入れることで、合計価値をより高くできる場合が考慮されないですね。

プログラマ専用SNS ミクプラ

入力値から選択する方法

入力値から選択する方法

Re: 入力値から選択する方法

Re: 入力値から選択する方法

Re: 入力値から選択する方法

Re: 入力値から選択する方法

Re: 入力値から選択する方法