問題はこちら
No.527 ナップサック容量問題 - yukicoder
まずは普通に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;
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
