C++ 贪心算法解决宝藏问题：最大化价值的背包策略

#include\x20\x3ciostream\x3e\n#include\x20\x3cvector\x3e\n#include\x20\x3calgorithm\x3e\n\nusing\x20namespace\x20std;\n\n//\x20定义金币结构体\nstruct\x20Coin\x20{\n\x20\x20int\x20weight;\n\x20\x20int\x20value;\n};\n\n//\x20贪心算法实现函数\nint\x20getMaxValue(vector\x3cCoin\x3e\x26coins,\x20int\x20capacity)\x20{\n\x20\x20//\x20按照单位价格从高到低排序\n\x20\x20sort(coins.begin(),\x20coins.end(),\x20\x20{\n\x20\x20\x20\x20return\x20a.value\x20/\x20a.weight\x20\x3e\x20b.value\x20/\x20b.weight;\n\x20\x20});\n\x20\x20\n\x20\x20int\x20maxValue\x20=\x200;\n\x20\x20\n\x20\x20//\x20依次选择单位价格最高的金币\n\x20\x20for\x20(int\x20i\x20=\x200;\x20i\x20\x3c\x20coins.size();\x20i++)\x20{\n\x20\x20\x20\x20if\x20(capacity\x20\x3e=\x20coins[i].weight)\x20{\n\x20\x20\x20\x20\x20\x20maxValue\x20+=\x20coins[i].value;\n\x20\x20\x20\x20\x20\x20capacity\x20-=\x20coins[i].weight;\n\x20\x20\x20\x20}else\x20{\n\x20\x20\x20\x20\x20\x20maxValue\x20+=\x20capacity\x20*\x20(coins[i].value\x20/\x20coins[i].weight);\n\x20\x20\x20\x20\x20\x20break;\n\x20\x20\x20\x20}\n\x20\x20}\n\x20\x20\n\x20\x20return\x20maxValue;\n}\n\nint\x20main()\x20{\n\x20\x20int\x20N,\x20T;\n\x20\x20cin\x20\x3e\x3e\x20N\x20\x3e\x3e\x20T;\n\x20\x20\n\x20\x20vector\x3cCoin\x3e\x20coins(N);\n\x20\x20for\x20(int\x20i\x20=\x200;\x20i\x20\x3c\x20N;\x20i++)\x20{\n\x20\x20\x20\x20cin\x20\x3e\x3e\x20coins[i].weight\x20\x3e\x3e\x20coins[i].value;\n\x20\x20}\n\x20\x20\n\x20\x20int\x20maxValue\x20=\x20getMaxValue(coins,\x20T);\n\x20\x20cout\x20\x3c\x3c\x20maxValue\x20\x3c\x3c\x20endl;\n\x20\x20\n\x20\x20return\x200;\n