Lib/Knapsack Problem
O(NW)
code:cpp
signed main(void){
int n,w;
cin >> n >> w;
vector<vector<int>> vec(n,vector<int>(2,0));
rep(i,n){
cin >> veci0 >> veci1;
}
vector<vector<int>> dp(n+1,vector<int>(w+1,0));
for(int i=1;i<n+1;i++){
for(int j=1;j<w+1;j++){
//dpij
if(j-veci-10>=0){
dpij = max(dpi-1[j-veci-10]+veci-11,dpi-1j);
}else{
dpij = dpi-1j;
}
}
// cout << join(dpi," ") << endl;
}
cout << dpnw << endl;
}
重さwi,価値vi ->重さ総和W以下の最大値