题解 | #采药#类背包问题
采药
https://www.nowcoder.com/practice/d7c03b114f0541dd8e32ce9987326c16
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
int t[100],v[100];
while(cin>>n>>m)
{
int dp[m+1][n+1];
for(int i=1;i<=m;i++)
{
cin>>t[i]>>v[i];
}
for(int i=0;i<=m;i++)
for(int j=0;j<=n;j++)
{
if(i==0) dp[i][j]=0;
else if(t[i]<=j) dp[i][j]=max(dp[i-1][j-t[i]]+v[i],dp[i-1][j]);
else dp[i][j]=dp[i-1][j];
}
cout<<dp[m][n]<<endl;
}
return 0;
}
查看28道真题和解析