투자 문제 (동적 기획)

제목: m 개 프로젝트, n 원 돈, f (x, y) 는 x 개 프로젝트 가 y 원 돈 을 투자 하 는 효 익 을 나타 내 고 어떻게 투자 하여 효 익 을 가장 크게 하 는 지 물 었 다.
대상 함수: max {f (1, y1) + f (2, y2) +... + f (m, yn)};제약 조건: y1 + y2 +... + yn = n;
분석: 우 리 는 2 차원 배열 dp, dp [i] [j] 를 유지 하고 전 i 개 프로젝트 가 j 위안 의 최대 수익 을 투자 하 는 것 을 말한다. 동태 계획 을 사용 할 때 문 제 를 어떻게 하위 문제 로 나 누 는 지 고려 할 수 있다. 우 리 는 먼저 첫 번 째 프로젝트 에서 고려 한 다음 에 앞의 두 프로젝트 를 고려 한 다음 에 앞의 세 번 째 프로젝트 에서 m 에 x 위안 을 분배 하고 n - x 위안 의 최대 수익 은 dp [m - 1] [n - x] 이다.이렇게 하면 우 리 는 푸 시 방정식 을 얻 을 수 있다.

dp [x] [y] = max {f (x, i) + dp [x - 1] [y - i]} (i 의 수치 [0, y])

eg: 4 개 항목, 5 원, f (x, y) 가 있 습 니 다.

0,0,0,0,0,0,

0,11,12,13,14,15,

0,0,5,10,15,20,

0,2,10,30,32,40,

0,20,21,22,23,24

코드 구현:

#include 
#include 
using namespace std;
const int M = 5;
const int N = 6;
int MaxProfit(int dp[M][N],int f[M][N],int n,int money)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= money; j++)
		{
			dp[i][j] = 0;
			for (int k = 0; k <= j; k++)
			{
				if (dp[i][j] < f[i][k] + dp[i - 1][j - k])
					dp[i][j] = f[i][k] + dp[i - 1][j - k];
			}
		}
	}
	return dp[n][money];
}

int main(int argc, char** argv)
{
	int dp[M][N] = { 0 };
	int f[M][N] = { 0,0,0,0,0,0,
				   0,11,12,13,14,15,
				   0,0,5,10,15,20,
				   0,2,10,30,32,40,
				   0,20,21,22,23,24 };
	cout << MaxProfit(dp, f, 4, 5);
	system("pause");
	return 0;
}

max profit=61；

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

BFPTR 알고리즘 (서열 중 k 번 째 작은 숫자 구하 기)

1973 년 Blum, Floyd, Pratt, Rivest, Tarjan 과 함께 'Time bounds for selection' 이라는 논문 을 발표 하여 배열 에서 k 대 요소 의 평균 복잡 도 를 O (N)...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

투자 문제 (동적 기획)

좋은 웹페이지 즐겨찾기