#39826: [c++] dp


mu0975353917@gmail.com (Moon Chan)

學校 : 國立雲林科技大學
編號 : 188583
來源 : [49.216.88.200]
最後登入時間 :
2024-05-10 14:20:01
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; 
 
}
 
}
 
ZeroJudge Forum