JZTXT

动态规划 完全背包问题 -游戏最大伤害

发布时间 2023-06-28 19:56:43作者: 白露~

游戏角色, 有技能列表和魔法值, 求能造成的最大伤害, 例如:

输入skill_list: [{mana_cost:10,damage:10}, {mana_cost:12,damage:13}], current_mana: 20, 输出max_damage: 20

输入skill_list: [{mana_cost:10,damage:10}, {mana_cost:12,damage:13}], current_mana: 25, 输出max_damage: 26

输入skill_list: [{mana_cost:2,damage:5}, {mana_cost:4,damage:11}, {mana_cost:7,damage:20}], current_mana: 13, 输出max_damage: 36

 

这是一道完全背包问题

 

public class GameMaxDamage {

    public static void main(String[] args) {
        Map<Integer, Integer> test = new HashMap<>();
        test.put(2, 5);
        test.put(4, 11);
        test.put(7, 20);
        System.out.println(maxDamage(test, 13));

        Map<Integer, Integer> test2 = new HashMap<>();
        test2.put(10, 10);
        test2.put(12, 13);
        System.out.println(maxDamage(test2, 25));

        System.out.println(maxDamage(test2, 20));
    }


    public static int maxDamage(Map<Integer, Integer> map, int currentMana) {

        Set<Integer> manaCosts = map.keySet();

        int[] dp = new int[currentMana + 1];
        dp[0] = 0;

        for (Integer cost : manaCosts) {
            int damage = map.get(cost);
            for (int i = cost; i <= currentMana; i++) {
                if (i >= cost) {
                    dp[i] = Math.max(dp[i], dp[i - cost] + damage);
                }

            }
        }
        return dp[currentMana];

    }
}