会津オンラインジャッジ：A Thief

[みけCAT]

http://rose.u-aizu.ac.jp/onlinejudge/Pr ... 42&lang=jp
の問題を解こうとしたのですが、わからなくなりました。
動的計画法だとは思うのですが、品物が一つというのが気になります。
でもまだそれ以前の問題だと思います。
ヒントがあれば幸いです。
お願いします。

コード:

#include <stdio.h>
#include <string.h>

typedef struct {
	int omosa;
	int kati;
} treasure;

typedef struct {
	int last;
	int kati;
} content;

int main(void) {
	int dataset;
	int w;
	int n;
	treasure takara[1000];
	int i,j;
	content nakami[1001];
	char exist[1000];
	int max,size;
	dataset=1;
	while(1) {
		scanf("%d",&w);
		if(w==0)return 0;
		scanf("%d",&n);
		for(i=0;i<n;i++) {
			scanf("%d,%d",&takara[i].kati,&takara[i].omosa);
		}
		memset(nakami,0,sizeof(nakami));
		for(i=0;i<n;i++) {
			for(j=1;j<=w;j++) {
				if(takara[i].omosa<=j) {
					if(takara[i].kati+nakami[j-takara[i].omosa].kati>
						nakami[j].kati) {
						nakami[j].last=i;
						nakami[j].kati=takara[i].kati
							+nakami[j-takara[i].omosa].kati;
					}
				}
			}
		}
		max=0;
		for(i=w;i>0;i--) {
			memset(exist,0,sizeof(exist));
			for(j=w;j>0;j-=takara[nakami[j].last].omosa) {
				if(exist[nakami[j].last])break;
				exist[nakami[j].last]=1;
			}
			if(j<=0) {
				if(nakami[i].kati>=max) {
					max=nakami[i].kati;
					size=i;
				}
			}
		}
		printf("Case %d:\n",dataset);
		printf("%d\n",max);
		printf("%d\n",size);
		dataset++;
	}
	return 0;
}

[五反田]

「ナップサック問題」で検索してみましょう。
あと、AOJの問題は、「AOJ 問題番号」でググルとたいてい解説なり、コードなりがヒットすると思うので、まずはそれを見てみるといいと思います。

[みけCAT]

やはりナップサック問題ですよね。
日経ソフトウェア2009.07の付録を参考にしようとしていたのですが...