ບັນຫາຫໍ່ ຄຳ


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Arcesium ປັດໃຈ ສີເທົາສີສົ້ມ Microsoft Myntra Ola Cabs PayU
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ຖະແຫຼງການບັນຫາ

ບັນຫາການຫໍ່ ຄຳ ລະບຸວ່າໃຫ້ ຄຳ ສັບຕາມ ລຳ ດັບເປັນການປ້ອນຂໍ້ມູນ, ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາ ຈຳ ນວນ ຄຳ ສັບທີ່ສາມາດ ເໝາະ ສົມກັບເສັ້ນດຽວໃນແຕ່ລະຄັ້ງ. ດັ່ງນັ້ນ, ສຳ ລັບການເຮັດສິ່ງນີ້ພວກເຮົາວາງການພັກຜ່ອນຕາມ ລຳ ດັບທີ່ໄດ້ກ່າວມາແລ້ວວ່າເອກະສານທີ່ພິມອອກຈະງາມ. ບັນນາທິການ ຄຳ ສັບເຊັ່ນ: Microsoft Office, Libre Office, ແລະເຄື່ອງມືເອກະສານອື່ນໆໃຊ້ການແບ່ງເສັ້ນເພື່ອເຮັດໃຫ້ເອກະສານມີຄວາມງາມ. ນີ້, ໂດຍງາມພວກເຮົາ ໝາຍ ຄວາມວ່າພວກເຮົາວາງພື້ນທີ່ໃນລັກສະນະທີ່ແຜ່ຂະຫຍາຍຢ່າງເທົ່າທຽມກັນ. ບໍ່ຄວນມີສາຍທີ່ມີສະຖານທີ່ເພີ່ມເຕີມແລະບາງບ່ອນມີ ຈຳ ນວນນ້ອຍໆ.

ນີ້, ພວກເຮົາຍັງສົມມຸດວ່າຄວາມຍາວຂອງ ຄຳ ສັບຂອງພວກເຮົາບໍ່ເກີນຂະ ໜາດ ເສັ້ນ. ພຽງແຕ່ເພື່ອເຮັດໃຫ້ສິ່ງຕ່າງໆມີຄວາມ ສຳ ຄັນກວ່າເກົ່າພວກເຮົາ ກຳ ລັງພິຈາລະນາຟັງຊັນຄົງທີ່ໃນ ຄຳ ຖາມທີ່ວ່າ (ຈຳ ນວນພື້ນທີ່ພິເສດ) ^ 3, ອີກຢ່າງ ໜຶ່ງ ມັນກໍ່ຈະງ່າຍເກີນໄປ. ຟັງຊັນຄ່າໃຊ້ຈ່າຍນີ້ອາດຈະແຕກຕ່າງກັນໄປຕາມ ຄຳ ຖາມທີ່ຖືກຖາມ.

ວິທີການຫໍ່ ຄຳ Dp

ຍົກຕົວຢ່າງ

ໃນນີ້, ພວກເຮົາຈະສະ ໜອງ ຈຳ ນວນ ຄຳ ສັບ, ຂະ ໜາດ ຂອງ ຄຳ ສັບ, ແລະຂະ ໜາດ ຂອງເສັ້ນເປັນການປ້ອນຂໍ້ມູນ.

number of words = 4

wordSize = { 3, 2, 2, 5}

lineSize = 6
28

ຄຳ ອະທິບາຍ: ພວກເຮົາສາມາດວາງ ຄຳ ທີ 1 ໃນເສັ້ນທີ 1 ດ້ວຍ 3 ຊ່ອງພິເສດ, ທີ 2 ແລະ ຄຳ ທີ 3 ຢູ່ເທິງເສັ້ນທີ 2 ມີ 1 ຊ່ອງພິເສດ, ແລະ ຄຳ ສຸດທ້າຍຢູ່ແຖວທີ 3 ບໍ່ມີພື້ນທີ່ເພີ່ມເຕີມ (ພວກເຮົາຈະບໍ່ພິຈາລະນາຊ່ອງຫວ່າງຫຼັງຈາກ ຄຳ ສຸດທ້າຍ ເປັນສະຖານທີ່ພິເສດ). ດັ່ງນັ້ນ, ການ ນຳ ໃຊ້ ໜ້າ ທີ່ຄ່າໃຊ້ຈ່າຍຂອງພວກເຮົາພວກເຮົາເຫັນວ່າຄ່າໃຊ້ຈ່າຍແມ່ນ 28.

number of words = 3

wordSize = { 1, 1, 1}

lineSize = 10
00

ຄຳ ອະທິບາຍ: ໃນທີ່ນີ້ພວກເຮົາສາມາດວາງ ຄຳ ທັງ ໝົດ ໃສ່ເສັ້ນດຽວກັນເຊັ່ນ: ເສັ້ນທີ 1 ແລະດັ່ງນັ້ນຄ່າໃຊ້ຈ່າຍ = 0.

 

ວິທີການ ສຳ ລັບບັນຫາຫໍ່ ຄຳ

ວິທີການ ທຳ ອິດທີ່ມາສູ່ຈິດໃຈແມ່ນວິທີແກ້ໄຂທີ່ໂລບທີ່ພວກເຮົາພຽງແຕ່ຍຶດ ຄຳ ເວົ້າຢູ່ໃນເສັ້ນດຽວ. ໃນເວລາທີ່ພວກເຮົາບໍ່ສາມາດວາງ ຄຳ ຢູ່ສາຍດຽວກັນ, ພວກເຮົາຍ້າຍໄປແຖວທີສອງ. ນີ້ເບິ່ງຄືວ່າຈະເຮັດວຽກໄດ້ດີ, ແຕ່ວ່າມັນມີຄວາມຈັບໃຈ. ສູດການຄິດໄລ່ນີ້ຈະບໍ່ສ້າງຜົນໄດ້ຮັບທີ່ດີທີ່ສຸດເພາະວ່າອາດຈະມີກໍລະນີເຊັ່ນວ່າຖ້າພວກເຮົາປ່ຽນພື້ນທີ່ພິເສດພວກເຮົາອາດຈະຈົບລົງດ້ວຍການແກ້ໄຂບັນຫາທົ່ວໂລກທີ່ດີຂື້ນ.

ຜົນໄດ້ຮັບໂດຍໃຊ້ວິທີການ Greedy

”cat is an animal”, line size = 6
65

 

ພຽງແຕ່ເພື່ອຄວາມເຂົ້າໃຈງ່າຍໆ, ພວກເຮົາໄດ້ສະແດງການປ້ອນຂໍ້ມູນເປັນ ຄຳ ສັບແທນ ຄຳ ທີ່ wordSize.

ຄຳ ອະທິບາຍ: ແມວ is_

                        an____

                        ສັດ

ໃນນີ້, ມີ 4 ຊ່ອງຫວ່າງຕື່ມອີກຢູ່ແຖວທີສອງແລະ 1 ຢູ່ແຖວທີສາມ.

ການຄິດໄລ່: 4 ^ 3 + 1 ^ 3 = 65

 

ມີວິທີແກ້ໄຂທີ່ດີກວ່າ,

cat___

ແມ່ນ an_

ສັດ

ໃຫ້ພວກເຮົາມີຄ່າໃຊ້ຈ່າຍທັງ ໝົດ 28 (3 ^ 3 + 1 ^ 3 + 0 ^ 3), ເຊິ່ງດີກ່ວາ 65.

ດຽວນີ້, ພວກເຮົາຈະແກ້ໄຂບັນຫາຫໍ່ ຄຳ ດ້ວຍການ ນຳ ໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ. ພວກເຮົາຮູ້ວ່າບັນຫາຂອງພວກເຮົາຕ້ອງການວິທີແກ້ໄຂທີ່ດີທີ່ສຸດໃນທົ່ວໂລກແລະລະບົບການຄິດໄລ່ກ່ອນ ໜ້າ ນີ້ຂອງພວກເຮົາໄດ້ພະຍາຍາມໃຫ້ພວກເຮົາມີຜົນດີທີ່ສຸດໃນທ້ອງຖິ່ນ. ໃນທີ່ນີ້ພວກເຮົາຈະພົບເຫັນພື້ນທີ່ພິເສດທີ່ປະຕິບັດໃນແຕ່ລະເສັ້ນ, ແລະດັ່ງນັ້ນຈະຊອກຫາຄ່າໃຊ້ຈ່າຍ ສຳ ລັບແຕ່ລະແຖວຕາມ ລຳ ດັບ. ພວກເຮົາຈະຮັກສາຕາຕະລາງ Extrarix ທີ່ຈະບອກ extraSpace ທີ່ເຫລືອຢູ່ໃນເສັ້ນ, ຄຳ ເວົ້າຈາກ i ຫາ j ແມ່ນຖືກຈັດຢູ່ໃນສາຍດຽວ. ຈາກນັ້ນຕໍ່ໄປພວກເຮົາຈະ ນຳ ໃຊ້ຕາຕະລາງ extraSpace ນີ້ເພື່ອຊອກຫາຄ່າໃຊ້ຈ່າຍຂັ້ນຕ່ ຳ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບບັນຫາຫໍ່ ຄຳ

#include <bits/stdc++.h>
using namespace std;

int wordWrap (int wordSize[], int n, int lineSize) 
{ 
  int extraSpace[n+1][n+1];
  int minCost[n+1];

  for (int i=1;i<=n;i++) 
  { 
    extraSpace[i][i] = lineSize - wordSize[i-1];
    for (int j=i+1;j<=n;j++) 
        extraSpace[i][j] = extraSpace[i][j-1] - wordSize[j-1] - 1; 
  }
  
  minCost[0] = 0; 
  for (int i = 1; i <= n; i++) 
  { 
    minCost[i] = INT_MAX;
    for (int j = 1; j <= i; j++) 
    { 
        int cost; // stores cost of storing words[i,j] in single line
        
        //if extraSpace required is negative, then we can't place
        //words[i,j] in a single line, else if we placed our last
        //word, then we don't consider extraSpace, else calculate
        //cost as per given cost function.
        if(extraSpace[j][i]<0)cost = INT_MAX;
        else if(i==n && extraSpace[j][i]>=0)cost = 0;
        else cost = extraSpace[j][i]*extraSpace[j][i]*extraSpace[j][i];
        
      if (minCost[j-1] != INT_MAX && cost != INT_MAX
      && (minCost[j-1] + cost < minCost[i])) 
        minCost[i] = minCost[j-1] + cost;
    }
  }
  
  return minCost[n];
} 

int main() 
{
    int t;cin>>t;
    while(t--) {
       int n;cin>>n;
       int wordSize[n];
       for(int i=0;i<n;i++)
            cin>>wordSize[i];
       int lineSize;cin>>lineSize;
       int ans = wordWrap(wordSize, n, lineSize);
       cout<<ans<<endl;
    }
}
3
4
3 2 2 6
6
3
1 1 1
10
4
1 1 1 1
5
28
0
0

Java Code ສຳ ລັບບັນຫາຫໍ່ ຄຳ

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{ 
  static int wordWrap (int wordSize[], int n, int lineSize) 
  { 
    int extraSpace[][] = new int[n+1][n+1]; 
    int minCost[] = new int[n+1];
  
    for (int i=1;i<=n;i++) 
    { 
      extraSpace[i][i] = lineSize - wordSize[i-1];
      for (int j=i+1;j<=n;j++) 
          extraSpace[i][j] = extraSpace[i][j-1] - wordSize[j-1] - 1; 
    } 
    
    	minCost[0] = 0; 
    	for (int i = 1; i <= n; i++) 
    	{ 
    		minCost[i] = Integer.MAX_VALUE;
    		for (int j = 1; j <= i; j++) 
    		{ 
    		    int cost; // stores cost of storing words[i,j] in single line
    		    
    		    //if extraSpace required is negative, then we can't place
    		    //words[i,j] in a single line, else if we placed our last
    		    //word, then we don't consider extraSpace, else calculate
    		    //cost as per given cost function.
    		    if(extraSpace[j][i]<0)cost = Integer.MAX_VALUE;
    		    else if(i==n && extraSpace[j][i]>=0)cost = 0;
    		    else cost = extraSpace[j][i]*extraSpace[j][i]*extraSpace[j][i];
    		    
    			if (minCost[j-1] != Integer.MAX_VALUE && cost != Integer.MAX_VALUE
    			&& (minCost[j-1] + cost < minCost[i])) 
    				minCost[i] = minCost[j-1] + cost;
    		}
    	}
  
    return minCost[n];
  } 

  public static void main(String args[]) 
  {
      Scanner sc = new Scanner(System.in);
      
      int t = sc.nextInt();
      while(t-- > 0) {
         int n = sc.nextInt();
         int wordSize[] = new int[n];
         for(int i=0;i<n;i++)
              wordSize[i] = sc.nextInt();
         
         int lineSize = sc.nextInt();
         int ans = wordWrap(wordSize, n, lineSize);
         System.out.println(ans);
      }
  }
} 

 

3 
4 
3 2 2 6
6 
3 
1 1 1 
10 
4 
1 1 1 1 
5 
28 
0 
0

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນທີ່ໃຊ້ເວລາ: O (n ^ 2)

ນີ້, ເນື່ອງຈາກວ່າວົງນອກຂອງພວກເຮົາແລ່ນຈາກ 1 ເຖິງ n ແລະວົງພາຍໃນຂອງພວກເຮົາແລ່ນຈາກ 1 ເຖິງ i, ພວກເຮົາມີຄວາມສັບສົນດ້ານເວລາ polynomial ຂອງ O (n ^ 2).

ຄວາມສັບສົນໃນອະວະກາດ: O (n ^ 2)

ນີ້, ຂບວນ ExtraSpace ຂອງພວກເຮົາແມ່ນຂບວນ 2D ເຊິ່ງມີຂະ ໜາດ N * N, ເຊິ່ງເຮັດໃຫ້ພວກເຮົາມີຄວາມສັບສົນໃນອະວະກາດຂອງ Poly (O ^ 2).