11981. 最小化目標(biāo)值與所選元素的差
難度中等15 收藏 分享 切換為英文 接收動(dòng)態(tài) 反饋
給你一個(gè)大小為m x n的整數(shù)矩陣mat和一個(gè)整數(shù)target。
從矩陣的 每一行 中選擇一個(gè)整數(shù)，你的目標(biāo)是 最小化 所有選中元素之 和 與目標(biāo)值target的 絕對(duì)差 。
返回 最小的絕對(duì)差 拦坠。
a和b兩數(shù)字的 絕對(duì)差 是a - b的絕對(duì)值。
記憶化搜索乃競(jìng)賽選手基本技能
我的解（超時(shí)）
- 想法是O(N^3)的貪心尋找一個(gè)局部最優(yōu)解个绍，做剪枝標(biāo)準(zhǔn)
- 再使用回溯法O(N^3)挽霉，輔以剪枝移盆，以優(yōu)化時(shí)間復(fù)雜度
class Solution:
def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
min_=[math.inf]
m,n=len(mat),len(mat[0])
#isvisited=[False]*m
#必須使用記憶化搜索，或者使用動(dòng)態(tài)規(guī)劃
#動(dòng)態(tài)具有最優(yōu)化準(zhǔn)則
#使用貪心+剪枝
dp=[[math.inf]*n for _ in range(m)]
for i in range(n):
dp[0][i]=target-mat[0][i]
for i in range(1,m):
for j in range(n):
for jj in range(n):
dp[i][j]=dp[i-1][jj]-mat[i][j] if abs(dp[i][j])>abs(dp[i-1][jj]-mat[i][j]) \
else dp[i][j]
min_[0]=min([abs(i) for i in dp[-1]])
#print(min_[0])
def dfs(sum_,i):
if i>=m:
min_[0]=min(min_[0],abs(target-sum_))
return
for j in range(n):
try:
if sum_+mat[i][j]-target>min_[0]:
continue
#剪枝也不行
dfs(sum_+mat[i][j],i+1)
except:
print(i,j)
dfs(0,0)
return min_[0]
- 競(jìng)賽難度之一：每個(gè)題的數(shù)種解法柜裸，沒(méi)有一個(gè)看懂的缕陕，易放棄
- 使用模擬不同的加和粱锐，可能由于set的去重效果使得時(shí)間復(fù)雜度較低
class Solution:
def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
f=set([0])
m,n=len(mat),len(mat[0])
for i in range(m):
g=set()
for j in f:
for jj in mat[i]:
g.add(j+jj)
f=g
ans=math.inf
for i in f:
ans=min(ans,abs(i-target))
return ans
*剪枝方案疙挺，加和大于target時(shí)記錄最小的大于target的值，加和小于target時(shí)怜浅，向set里更新铐然，最后只需要在大于target的最小值與target的差值，與集合與target差值的最小值比較即可恶座。
該題不需要記錄求解路徑搀暑，故不需要搜索算法，而是使用動(dòng)態(tài)規(guī)劃跨琳，結(jié)合移位運(yùn)算自点，加和可以使用位置表示，加x相當(dāng)于1左移x
class Solution:
def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
def to_binary_reversed(x):
ans=''
while x:
ans+=str(x%2)
x//=2
return ans
m,n=len(mat),len(mat[0])
f=[0]*m
for j in range(n):
f[0]|=1<<mat[0][j]
for i in range(1,m):
for j in range(n):
f[i]|=f[i-1]<<mat[i][j]
move=to_binary_reversed(f[-1])
ans=math.inf
for i in range(len(move)):
if move[i]=='1':
ans=min(ans,abs(i-target))
return ans
image.png
-
數(shù)學(xué)知識(shí)解題之：相加為某固定數(shù)脉让，那么這些數(shù)當(dāng)相等時(shí)乘積最大桂敛，當(dāng)這些數(shù)盡可能平均分散在兩側(cè)時(shí)成績(jī)最小。
-
由上面的定理可知溅潜，當(dāng)sum=p時(shí)术唬，該（sum/n）^n乘積最大，如何最大化該表達(dá)式滚澜，通過(guò)求導(dǎo)以及代數(shù)得粗仓，sum/n=e時(shí)最大，帶入整數(shù)2设捐，3借浊。得sum/n=3時(shí)，乘積最大萝招，即三等時(shí)最大蚂斤。
待補(bǔ)題與代碼
