欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷—P1616 疯狂的采药(完全背包问题)

程序员文章站 2022-07-16 12:30:03
...

洛谷—P1616 疯狂的采药(完全背包问题)

#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;
}
相关标签: 动态规划