问题解决，邻居索引不相同的 n 个数组列表的一个元素的最小总和

Question

我得到这样的问题解决问题：“你决定去商场买衬衫和/或裤子和/或鞋子。在商场里有 N 家不同的商店。每家商店都包含这三种商品，但价格不同。现在你有 2 个习惯：从每家商店只购买一件商品如果您已经从当前商店附近的商店购买了该商品，请不要从当前商店购买相同的商品。你意识到找钱很难，所以你想尽量减少你在购物上的总支出。”示例 3（N 个店铺） 1 50 50（店铺 1 的衬衫、裤子和鞋子的成本） 48 50 50（店铺 2 的衬衫、裤子和鞋子的成本） 1 50 50（衬衫、裤子和鞋子的成本）在商店 3)所以最低成本是52，我在1号店买衬衫，2号店买裤子/鞋子，3号店买衬衫。我不能在2号店买衬衫，因为我以前在1号店买衬衫。我的第一个逻辑是列出所有可能的列表，相邻商店中没有相同的项目，然后我会搜索最低成本...但我遇到了时间限制问题...有什么想法可以解决吗？对不起，如果我的英语不好......如果你们回应并回答，非常感谢你......public class Solution {static ArrayList<ArrayList<Integer>> data;static int min;static int sum;static int n;static void permutation(int x, int y){    if(x==n-1){        sum+=data.get(x).get(y-1);        if(sum<min)            min = sum;    }    else{        sum+=data.get(x).get(y-1);        if(y==1){            permutation(x+1,2);            permutation(x+1,3);        }        else if(y==2){            permutation(x+1,1);            permutation(x+1,3);        }        else if(y==3){            permutation(x+1,1);            permutation(x+1,2);        }    }    sum-=data.get(x).get(y-1);}static int GetMinCost(ArrayList<ArrayList<Integer>> data){    sum = 0;    min = Integer.MAX_VALUE;    permutation(0,1);    permutation(0,2);    permutation(0,3);    return min;} static final Scanner scanner = new Scanner(System.in);public static void main(String[] args) {           int t = scanner.nextInt();    for(int i=0; i<t; i++){        n = scanner.nextInt();                    data = new ArrayList<>();                   for(int j=0; j<n; j++){            ArrayList<Integer> cost = new ArrayList<>();            cost.add(scanner.nextInt());            cost.add(scanner.nextInt());            cost.add(scanner.nextInt());            data.add(cost);        }                   System.out.println(GetMinCost(data));               }       }}

Answer 1

我认为一个简单的递归排列函数就足够了 - 您只需要跟踪选择的最后一个项目并将其从下一个商店中排除。

下面是一些 Java 代码来说明：

static int minCost(int[][] prices, int store, int cost, int lastItem)

{

    if(store==prices.length) 

        return cost;

    int min = Integer.MAX_VALUE;

    for(int item=0; item<prices[store].length; item++)

    {

        if(item != lastItem)

            min = Math.min(min, minCost(prices, store+1, cost+prices[store][item], item));

    }

    return min;

}

public static void main(String[] args)

{

    int[][] prices1 = {{1,50,50},{48,50,50},{1,50,50}};             

    System.out.println(minCost(prices1, 0, 0, -1));

    int[][] prices2 = {{1,50,50},{48,50,50},{1,50,50},{4,3,5},{20,1,20}};               

    System.out.println(minCost(prices2, 0, 0, -1));

}

输出：

52

58

Answer 2

假设我正确理解了这个问题，下面是我将如何在预填充的商店数组中解决它。我们找到每个存储数组中的最小值，并通过存储和比较它来排除之前存储中已经使用过的索引。

private int stores[][]={{1,50,50},{48,50,50},{1,50,50},{4,3,5},{20,1,20}};

public void solve() {

    int cost=0;

    int lastItemPurchased=-1;

    for (int storeIndex = 0; storeIndex < stores.length; storeIndex++) {

        int lowestPriceInStoreIndex=getMinValueIndex(stores[storeIndex],lastItemPurchased);

        cost+=stores[storeIndex][lowestPriceInStoreIndex];

        lastItemPurchased=lowestPriceInStoreIndex;

    }

    System.out.println("Cost: "+cost);

}

public int getMinValueIndex(int[] numbers,int indexToExclude){

    int minValue = 0;

    for(int i=1;i<numbers.length;i++){

        if(i==indexToExclude)

            continue;

        if(numbers[i] < numbers[minValue]||minValue==indexToExclude){

            minValue = i;

        }

    }

    return minValue;

}

这输出 75，因为它应该是 1+50+1+3+20。