洛谷—P1616 疯狂的采药(完全背包问题)
程序员文章站
2022-07-16 12:30:03
...
#include<iostream>
using namespace std;
int dp[100010];
int value[10010];
int Time[10010];
int t, n;
int max(int a, int b)
{
return a > b ? a : b;
}
int ks(int t)
{
for (int i = 1; i <= t; ++i)
for (int j = 0; j < n; ++j)
if (i >= Time[j])
dp[i] = max(dp[i], dp[i - Time[j]]+value[j]);
return dp[t];
}
int main()
{
cin >> t >> n;
for (int i = 0; i < n; ++i)
cin >> Time[i] >> value[i];
//for (int i = 1; i <= t; ++i)
//dp[i] = -1;
/*for (int i = 0; i < n; ++i)
for (int j = t; j >= time[i]; --j)
for (int k = 0; k*time[i] <= j; ++k)
dp[j] = max(dp[j], dp[j - k * time[i]] + k * value[i]);
cout << dp[t];*/
cout << ks(t);
//while (1);
return 0;
}
上一篇: 动态规划求解"疯狂的采药"问题(洛谷P1616题题解,Java语言描述)
下一篇: 背包