решение задачи, минимальная сумма одного элемента из n arraylist, где индекс соседей не совпадает - PullRequest
Новая
       42

решение задачи, минимальная сумма одного элемента из n arraylist, где индекс соседей не совпадает

0 голосов
/ 07 сентября 2018

У меня такой вопрос для решения проблем:

"Вы решаете пойти в торговый центр, чтобы купить рубашки и / или брюки и / или обувь. В торговом центре есть 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));           
    }       
}
}

Ответы [ 2 ]

0 голосов
/ 07 сентября 2018

Я думаю, что простой рекурсивной функции перестановки будет достаточно - вам просто нужно отследить последний выбранный элемент и исключить его из следующего магазина.

Вот пример кода 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
0 голосов
/ 07 сентября 2018

Предполагая, что я правильно понял проблему, вот как я могу решить ее в предварительно заполненном массиве магазинов. Мы находим наименьшее значение в каждом массиве хранилища и исключаем индекс, если он уже использовался ранее в предыдущем хранилище, сохраняя и сравнивая его. 

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.

...