编辑代码

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int coinCollect(vector<int>& coins, int target) {
    // 初始化dp数组
    vector<int> dp(target + 1, INT_MIN);
    dp[0] = 0;

    // 遍历目标价值范围，计算dp数组的值
    for (int i = 1; i <= target; i++) {
        // 遍历硬币的价值
        for (int coin : coins) {
            // 将硬币的价值纳入考虑，求得收集总价值为i时所需的最小硬币数量
            if (i >= coin && dp[i - coin] != INT_MIN) {
                dp[i] = max(dp[i], dp[i - coin] + 1);
            }
        }
    }
    // 返回dp数组中的最大值，即最大的收集总价值
    for (int i = target; i >= 0; i--) {
        if (dp[i] != INT_MIN) {
            return dp[i];
        }
    }
    return 0;  // 没有收集到任何硬币
}
int main() {
    // 硬币价值数组
    vector<int> coins = {1, 2, 5, 10, 20, 30};
    // 需要收集的价值
    int target = 50;
    int result = coinCollect(coins, target);
    cout << "最大总价值为: " << result << endl;
    return 0;
}