问题解决，邻居索引不相同的 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){&nbsp; &nbsp; if(store==prices.length)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return cost;&nbsp; &nbsp; int min = Integer.MAX_VALUE;&nbsp; &nbsp; for(int item=0; item<prices[store].length; item++)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if(item != lastItem)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = Math.min(min, minCost(prices, store+1, cost+prices[store][item], item));&nbsp; &nbsp; }&nbsp; &nbsp; return min;}public static void main(String[] args){&nbsp; &nbsp; int[][] prices1 = {{1,50,50},{48,50,50},{1,50,50}};&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; System.out.println(minCost(prices1, 0, 0, -1));&nbsp; &nbsp; int[][] prices2 = {{1,50,50},{48,50,50},{1,50,50},{4,3,5},{20,1,20}};&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; System.out.println(minCost(prices2, 0, 0, -1));}输出：5258

Answer 2

假设我正确理解了这个问题，下面是我将如何在预填充的商店数组中解决它。我们找到每个存储数组中的最小值，并通过存储和比较它来排除之前存储中已经使用过的索引。private int stores[][]={{1,50,50},{48,50,50},{1,50,50},{4,3,5},{20,1,20}};public void solve() {&nbsp; &nbsp; int cost=0;&nbsp; &nbsp; int lastItemPurchased=-1;&nbsp; &nbsp; for (int storeIndex = 0; storeIndex < stores.length; storeIndex++) {&nbsp; &nbsp; &nbsp; &nbsp; int lowestPriceInStoreIndex=getMinValueIndex(stores[storeIndex],lastItemPurchased);&nbsp; &nbsp; &nbsp; &nbsp; cost+=stores[storeIndex][lowestPriceInStoreIndex];&nbsp; &nbsp; &nbsp; &nbsp; lastItemPurchased=lowestPriceInStoreIndex;&nbsp; &nbsp; }&nbsp; &nbsp; System.out.println("Cost: "+cost);}public int getMinValueIndex(int[] numbers,int indexToExclude){&nbsp; &nbsp; int minValue = 0;&nbsp; &nbsp; for(int i=1;i<numbers.length;i++){&nbsp; &nbsp; &nbsp; &nbsp; if(i==indexToExclude)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue;&nbsp; &nbsp; &nbsp; &nbsp; if(numbers[i] < numbers[minValue]||minValue==indexToExclude){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; minValue = i;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return minValue;}这输出 75，因为它应该是 1+50+1+3+20。