1017 Buy Fish 官方题解

题目回顾

Kirk 有一个”理想“（并没有）， 就是以后能有一个属于自己水族馆。无奈啥啥都要钱，这让 Kirk 很烦恼，经过一大波的规划后，买了一大堆水族馆的设备，现在就差鱼还没有买了。可怜的Kirk兜里只剩下为数不多的 money，为了尽可能地让 Kirk 开心你能为 Kirk 制定一个卖鱼的方案，使得 cute 值拉满吗？ 市场上的鱼有很多种，每种鱼有不同的价格（price）和可爱程度（cute）。

题目分析

本题的目的是在给定的money有限的情况下，去买不同种类不同价格的鱼，不同种类的鱼有一个不同的cute值。看到这里，很容易去使用贪心算法，算每种鱼单价下的cute，据此来选择。实际上贪心算法确实可以解出，但是存在一定的局限性。这里就使用动态规划中的背包算法来解决问题。对于不同的鱼我们可以重复购买，并不是单一的选或者不选择，但是也没有限定每种鱼可以购买的数量，所以可以得出这是一个完全背包的问题。想到使用完全背包此题基本已经解决。

可行代码

代码仅供参考

#include <iostream>
using namespace std;
int main(){
	int money, kinds;
	cin >> money >> kinds;
	int price[kinds+5], cute[kinds + 5];
	for(int i = 1; i <= kinds; i++)
		cin >> price[i] >> cute[i];
	int dp[money + 5] = {0};
	for(int i = 1; i <= kinds; i++)
		for(int j = price[i]; j <= money; j++)
				dp[j] = max(dp[j], dp[j - price[i]] + cute[i]);
	cout << dp[money];
	return 0;
}

END 祝大家学习愉快