POJ 2063 Investment DP(完全背包）

本文主要是介绍POJ 2063 Investment DP(完全背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：John有一笔钱，他想投资来获得利润。现在给出他的本金，准备投资的时间长，可以购买的基金种类，以及每一种基金的购价与利息。求他可以获得的最大收益。每一年的利息算入下一年的本金。
题解: 由于基金的购价都是1000的倍数，所以可以将本金除1000来缩小背包。

#include <cstdlib>
#include <iostream>
using namespace std;int dp[450000], w[11], v[11];int main()
{int n, capital, year, bond, temp;cin >> n;while ( n-- ){int i, j;cin >> capital >> year >> bond;for ( i = 0; i < bond; i++ ){cin >> w[i] >> v[i];w[i] /= 1000;}memset ( dp, 0, sizeof(dp) ); while ( year-- ){int m = capital / 1000;for ( i = 0; i < bond; i++ ){for ( j = w[i]; j <= m; j++ ){temp = dp[j-w[i]] + v[i];if ( temp > dp[j] )dp[j] = temp;}}capital += dp[m];m = capital / 1000;}cout << capital << endl;}return 0;
}

这篇关于POJ 2063 Investment DP(完全背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---