yukicoder No.527 ナップサック容量問題

まずは普通に01ナップサック問題を解く必要があるが、そのときのDPのやりかたとして２通り考えられる。

1つ目は、問題文の表にあるように、d[i]に「重さi以内で得られる価値の最大値」を保存する方法

#define max(p,q)(p>q?p:q)
d[200000];
v,w,n;
i,j,t,m;
main(){
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d%d",&v,&w);
		for(j=100000;j>=w[i];j--)d[j]=max(d[j],d[j-w]+v);
	}
	scanf("%d",&t);
	for(i=1;i<100000;i++)if(d[i]>=t){printf("%d\n",m=i);break;}
	for(;i<=100000;i++)if(d[i]>d[m]){printf("%d\n",i-1);return 0;}
	puts("inf");
}

もう1つは、d[i]に「価値iを得るための重さの最小値」を保存する方法
こちらは漸化式が見えるまで少し時間がかかった

#define INF (3LL<<29)
#define min(p,q)(p<q?p:q)
a[1<<17],*d=a+1000;//添字がマイナスになることがあるのでindexをずらした
v,w,n;
i,j,t;
main(){
	scanf("%d",&n);
	for(j=1;j<100010;j++)d[j]=INF;
	for(i=0;i<n;i++){
		scanf("%d%d",&v,&w);
		for(j=100010;j;j--)d[j]=min(d[j],d[j-v]+w);
	}
	scanf("%d",&t);
	printf("%d\n",d[t]?:1);
	printf(d[t+1]==INF?"inf":"%d",d[t+1]-1);
}

後者の方が出力が簡単なので、初期化を省略できればこちらのほうが短くなりそう。
初期化を省略すると0とINFの区別をうまくつけることが必要になるが、INF以外の値に更新されるのはΣvi以下に限るので、このことからつぎのように書ける。

a[1<<17],*d=a+1000;
v,w,n,s,m;
i,j,t;
main(){
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d%d",&v,&w);
		s+=v;
		for(j=s;j;j--)if(!d[j]|d[j]>d[j-v]+w)d[j]=d[j-v]+w;
	}
	scanf("%d",&t);
	printf(d[t+1]?"%d\n%d":"%d\ninf",d[t]?:1,d[t+1]-1);
}

入力の工夫

scanf("%d",&n);
for(i=0;i<n;i++){
	scanf("%d%d",&v,&w);
	s+=v;
	for(j=s;j;j--)if(!d[j]|d[j]>d[j-v]+w)d[j]=d[j-v]+w;
}
scanf("%d",&t);
//↑これが　↓こう
for(;~scanf("%d%d",&w,&t);){
	for(j=s;j;j--)if(!d[j]|d[j]>d[j-v]+w)d[j]=d[j-v]+w;
	s+=v=t;
}

その他の細々した工夫、ループ圧縮などを取り入れて

d[1<<17];
v,w,t;s,j;
main(m){
	for(;j?d[j]>(m=d[j>v?j-v:0]+w)|!d[j]?d[j]=m:0,j--:(j=s+=v=t,~scanf("%d%d",&w,&t));m=d[t+1]);
	printf(m?"%d\n%d":"%d\ninf",d[t]?:1,m-1);
}

161B

メモ

yukicoderでゆるふわgolf

yukicoder No.527 ナップサック容量問題