2021-3-13-[プログラミング問題]風電場ファン発電スケジューリング問題

ある风空港の台风机ごとの発电量と升圧ステーションまでの距离はそれぞれ异なって、例えば风机1、距离は30で、発电量は20です;ファン2、距離20、発電量18;ファン3、距離35、発電量25;ファン4、距離40、発電量30;全ファンの総距離が一定の場合(例えば距離<=100)、最大発電量を求める.入力:1行目:台風1機当たり距離2行目:台風1機当たり発電量3行目:総距離k例えば:30 20 35 40 20 18 25 50出力:38
//問題解:リュックの問題、距離は物の重さ、発電量は物の価値、総距離はリュックの容量と見ることができる

#include 
#include 
#include 
#include 
#include 

using namespace std;

class Solution
{
     
public:
	int findMax(vector<int>& dists, vector<int> &values, int k)
	{
     
		int n = dists.size() - 1;
		vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
		for (int i = 1; i <= n; i++)
		{
     
			for (int j = 1; j <= k; j++)
			{
     
				if (j >= dists[i])
				{
     
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - dists[i]] + values[i]);
				}
				else
				{
     
					dp[i][j] = dp[i - 1][j];
				}
			}
		}

		return dp[n][k];
	}
};


int main()
{
     
	Solution sol; 
	string str;

	vector<int> dists;
	dists.push_back(0);
	vector<int> values;
	values.push_back(0);

	getline(cin, str);
	while (str.find(' ') != -1)
	{
     
		int pos = str.find(' ');
		int num = stoi(str.substr(0, pos));
		dists.push_back(num);
		str = str.substr(pos + 1);
	}

	dists.push_back(stoi(str));

	getline(cin, str);
	while (str.find(' ') != -1)
	{
     
		int pos = str.find(' ');
		int num = stoi(str.substr(0, pos));
		values.push_back(num);
		str = str.substr(pos + 1);
	}
	values.push_back(stoi(str));

	int k = 50;
	cin >> k;

	int res = sol.findMax(dists, values, k);
	
	
	cout << res << endl;
	
	return 0;
}