全て調べれば良い
その際に工夫が必要
可能な限り選択肢を広げてどちらが大きいか調べていく
つまりi番目を使った場合の最大値と使わなかった場合をどちらか大きいか式にすることを繰り返していくと最後にi=nになった時にres(n,x)=0となって全ての項が数字になる
maxを使用
数が3の場合
(w,v)=(1,2),(2,3),(1,3) で重さの上限を3とするとres(i番目以降,重さの上限)
res(0,3)=
max(res(1,3),res(1,2)+2)=
max(max(res(2,3),res(2,1)+3),max(res(2,2)+2,res(2,0)+2+3)))=
max(max(max(res(3,3),res(3,2)+3),max(res(3,1)+3,res(3,0)+3+3),max(max(res(2,2)+2,res(3,1)+5),(res(2,0)+2+3))
=res(3,0)+6
=6
みたいな感じにする
#include<　algorithm　>
#include<　iostream　>
using namespace std;
int n,x, w[100],v[100];
int rec(int i, int j){
int res;
if (i == n){ res = 0; }
else if (j < w[i]){
res = rec(i + 1, j);
}
else{ res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]); }
return res;
}
int main(){
cin >> n>>x;
for (int i = 0; i < n; i++){
cin >> w[i] >> v[i];
}
cout<<　rec(0, x);
getchar();
getchar();

}