アジアICPC瀋陽予選Dawn-K's water完全バックパック列挙

アジアICPC瀋陽予選Dawn-K's water完全バックパック列挙

入力

出力

例入力

例出力

解決構想

ACコード

文章を簡単にするために、原題は原題リンクの試合ページを直接見てください.
入力
複数のサンプル試験は、第1行にnおよびmが与えられ、それぞれ物品の種類数および下限重量を表す.次のn行は、それぞれpおよびcを与え、それぞれ価値および重量を表し、スペースで区切られる.
しゅつりょく
購入したm重量物の最小価値bを求め、各テストサンプルに1行出力する:必要な価値bと購入した重量をスペースで分ける
サンプル入力
3 3 2 1 3 1 1 1 3 5 2 3 1 2 3 3
サンプル出力
3 3 3 6
解決策
「完全バックパックの問題」に「多重部分と(列挙)」の問題を加え、ここでは説明しません.参考記事はここをクリックしてください.
ACコード

#include
#include 
const int maxn = 1019;
typedef long long int ll;
ll mark[10019],w[maxn],v[maxn];
ll n,m;
inline ll min(ll a,ll b){
	if(a>b)return b;
	return a;
}
int main(){
	ll a,b;
	ll INF;
	while(scanf("%lld%lld",&n,&m)!=EOF){
		a = b = 0;
		memset(mark,63,sizeof(mark));
		INF = mark[10];
	for(int i = 0;i<n;++i)
			scanf("%lld%lld",&v[i],&w[i]);
	mark[0]=0;
	for(int i = 0;i<n;++i)
		for(int j = w[i];j<=10000;++j){
			if(mark[j-w[i]]<INF)
				mark[j] = min(mark[j],mark[j-w[i]]+v[i]);
		//	printf("mark[%d]:%llu
",j,mark[j]);		
		}
	b = INF;	
	for(int i = m;i<=10000;++i){
		if(mark[i]<=b){
			b = mark[i];
			a = i;
		}
	}
	printf("%lld %lld
",b,a);
	}
	return 0; 
}