b184. 5. 裝貨櫃問題 -- 97學年度高雄市資訊學科能力競賽 | From: [36.235.73.56] | 發表日期 : 2024-04-03 00:13

#include<bits/stdc++.h> 

using namespace std;

int main()

{

int n,W=100;

while(cin>>n)

{

vector<int> w(n+1),v(n+1);

w[0]=0;

v[0]=0;

for(int i=1;i<=n;i++)

{

cin>>w[i];

cin>>v[i]; 

}

long long int dp[n+1][W+1]; 

for(int i=0;i<=n;i++)

{

for(int j=0;j<=W;j++)

{

dp[i][j]=0;

}

}

for(int i=1;i<=n;i++)

{

for(int j=1;j<=W;j++)

{

//cout<<i<<j<<" ";

if(j<w[i])

{

dp[i][j]=dp[i-1][j];

}

else

{

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);

}

}

}

 

 

cout<<dp[n][W]<<endl; 

 

}

 

}