我得到這樣的問題解決問題：“你決定去商場買襯衫和/或褲子和/或鞋子。在商場里有 N 家不同的商店。每家商店都包含這三種商品，但價格不同?，F在你有 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 回答
鳳凰求蠱
TA貢獻1825條經驗 獲得超4個贊
我認為一個簡單的遞歸排列函數就足夠了 - 您只需要跟蹤選擇的最后一個項目并將其從下一個商店中排除。
下面是一些 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
蠱毒傳說
TA貢獻1895條經驗 獲得超3個贊
假設我正確理解了這個問題，下面是我將如何在預填充的商店數組中解決它。我們找到每個存儲數組中的最小值，并通過存儲和比較它來排除之前存儲中已經使用過的索引。
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。
添加回答
舉報
0/150
提交
取消