动态编程的代码中有什么错误？

s6fujrry 于 2021-09-13 发布在 Java

关注(0)|答案(3)|浏览(336)

你好，这是我第一次在这个社区发帖
因此，我需要做的是：
编写一个函数cansum（），该函数接受一个目标和一个数字数组作为参数。
函数应返回一个布尔值，指示是否可以使用数组中的数字生成目标和。
可以根据需要多次使用数组的元素
您可以假设所有输入的数字都是非负的。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        System.out.println(canSum(7, new int[]{2, 3}));         //true
        System.out.println(canSum(7, new int[]{5, 3, 4, 7}));   //true
        System.out.println(canSum(7, new int[]{2, 4}));         //false
        System.out.println(canSum(8, new int[]{2, 3, 5}));      //true
        System.out.println(canSum(300, new int[]{7, 14}));      //false

    }
    private static Map<Integer, Boolean> memo = new HashMap<>();

    public static boolean canSum(int target, int[] arr){

        if(memo.containsKey(target)) return memo.get(target);
        if(target == 0) return true;
        if(target < 0) return false;

        for(int i = 0; i< arr.length;i++){
            int remainder = target - arr[i];
            if(canSum(remainder,arr)){
                memo.put(target, true);
                return true;
            }
        }
        memo.put(target,false);
        return false;
    }

程序输出：真
应该是什么时候：真假假假

Java dynamic-programming

来源：https://stackoverflow.com/questions/68542461/what-is-wrong-in-this-code-for-dynamic-programming

3条答案

按热度按时间

xzv2uavs1#

你的问题是你从来没有清理过你的账户 Map<Integer, Boolean> memo 在方法调用之间。如果可以使用true或false生成求和，则保存的Map仅对一个方法运行有效，因此代码不应在不同调用之间重用同一Map。
一个简单的解决方法是在每次调用后手动清除Map：

System.out.println(canSum(7, new int[] { 2, 3 })); //true
memo.clear();
System.out.println(canSum(7, new int[] { 5, 3, 4, 7 })); //true
memo.clear();
System.out.println(canSum(7, new int[] { 2, 4 })); //false
memo.clear();
System.out.println(canSum(8, new int[] { 2, 3, 5 })); //true
memo.clear();
System.out.println(canSum(300, new int[] { 7, 14 })); //false
memo.clear();

将创建输出

true
true
false
true
false

更优雅的解决方案是不使用字段存储Map，而是在需要时在内部创建Map。您可以使用以下两种方法完成此操作，例如：

public static boolean canSum(int target, int[] arr) {
    Map<Integer, Boolean> memo = new HashMap<>();
    return canSum(target, arr, memo);
}

private static boolean canSum(int target, int[] arr, Map<Integer, Boolean> memo) {
    if (memo.containsKey(target)) {
        return memo.get(target);
    }
    if (target == 0) {
        return true;
    }
    if (target < 0) {
        return false;
    }

    for (int i = 0; i < arr.length; i++) {
        int remainder = target - arr[i];
        if (canSum(remainder, arr, memo)) {
            memo.put(target, true);
            return true;
        }
    }
    memo.put(target, false);
    return false;
}

赞(0）回复(0）举报 2021-09-13

juzqafwq2#

不要把备忘录当作静态的

public class Main {
    public static void main(String[] args) {
        System.out.println(canSum(7, new int[]{2, 3}));         //true
        System.out.println(canSum(7, new int[]{5, 3, 4, 7}));   //true
        System.out.println(canSum(7, new int[]{2, 4}));         //false
        System.out.println(canSum(8, new int[]{2, 3, 5}));      //true
        System.out.println(canSum(300, new int[]{7, 14}));      //false

    }
    /* 
     * private static Map<Integer, Boolean> memo = new HashMap<>(); 
     * 
     * It will check for first one and will store the result, then for rest
     * operation it will rend stored data only
     */

    public static boolean canSum(int target, int[] arr){

        Map<Integer, Boolean> memo = new HashMap<>();

        if(memo.containsKey(target)) return memo.get(target);
        if(target == 0) return true;
        if(target < 0) return false;

        for(int i = 0; i< arr.length;i++){
            int remainder = target - arr[i];
            if(canSum(remainder,arr)){
                memo.put(target, true);
                return true;
            }
        }
        memo.put(target,false);
        return false;
    }
}

赞(0）回复(0）举报 2021-09-13

3zwjbxry3#

自从你离开后，它就不起作用了 memo map是一个静态成员变量，它也将包含所有以前的迭代。
所以当你这么做的时候 memo.put() 在最后一行中，它添加了不同的组合，这些组合可以直接在中重用 memo.containsKey .
可以在该函数中移动该变量。它应该开始正常工作。

赞(0）回复(0）举报 2021-09-13