單調隊列優化的背包問題

對于背包問題,經典的背包九講已經講的很明白了,本來就不打算寫這方面問題了。

但是吧。

我發現,那個最出名的九講竟然沒寫隊列優化的背包。。。。

那我必須寫一下咯嘿嘿,這么好的思想。

?

我們回顧一下背包問題吧。

?

01背包問題?


題目?
有N件物品和一個容量為V的背包。第i件物品的費用是c[i],價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量,且價值總和最大。?

這是最基礎的背包問題,特點是:每種物品僅有一件,可以選擇放或不放。?

f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是:

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。?

就是說,對于本物品,我們選擇拿或不拿

比如費用是3.

相關圖解:

我們求表格中黃色部分,只和兩個黑色部分有關

拿了,背包容量減少,我們價值加上減少后最大價值。

不拿,最大價值等于沒有這件物品,背包不變,的最大價值。

完全背包問題?


題目?
有N種物品和一個容量為V的背包,每種物品都有無限件可用。第i種物品的費用是c[i],價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量,且價值總和最大。?


基本思路?
這個問題非常類似于01背包問題,所不同的是每種物品有無限件。

f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}

圖解:

因為我們拿了本物品還可以繼續拿無限件,對于當前物品,無論之前拿沒拿,還可以繼續拿,所以是f[i][v-c[i]]+w[i]

?

換一個角度說明這個問題為什么可以f[i][v-c[i]]+w[i],也就是同一排。

其實是這樣的,我們對于黃色部分,也就是當前物品,有很多種選擇,可以拿一個,兩個。。。一直到背包容量不夠了。

也就是說,可以不拿,也就是J1,可以拿一個,也就是G1+w[i],也可以拿兩個,也就是D1+2w[i],拿三個,A1+3w[i]。

但是我們看G2,G2其實已經是之前的最大了:A1+2w[i],D1+w[i],G1他們中最大的,對么?

既然G2是他們中最大的。

我們怎么求J2?

是不是只要求G2+w[i]和J1的最大值就好了。

因為G2把剩下的情況都保存好了。

?

多重背包問題?(正文)


題目?
有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用,每件費用是c[i],價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量,且價值總和最大。?

?

和之前的完全背包不同,這次,每件物品有最多拿n[i]件的限制。

思路一:我們可以把物品全都看成01背包:比如第i件,我們把它拆成n[i]件一樣的單獨物品即可。

思路二:思路一時間復雜度太高。利用二進制思路:一個n位二進制,能表示2^n種狀態,如果這些狀態就是拿了多少物品,我們可以把每一位代表的數都拿出來,比如n[i]=16,我們把它拆成1,2,4,8,1,每一堆物品看成一個單獨物品。

為什么最后有個一?因為從0到16有十七種狀態,四位不足以表示。我們最后補上第五位1.

把拆出來的物品按01背包做即可。

思路三:我們可以利用單調隊列:

https://blog.csdn.net/hebtu666/article/details/82720880

再回想完全背包:為什么可以那么做?因為每件物品能拿無限件。所以可以。而多重背包因為有了最多拿多少的限制,我們就不敢直接從G2中拿數,因為G2可能是拿滿了本物品以后才達到的狀態?。

比如n[i]=2,如果G2的狀態是2w[i],拿了兩個2物品達到最大值,我們的J2就不能再拿本物品了。

如何解決這個問題?就是我給的網址中的,雙端單調隊列

利用窗口最大值的思想。

大家想想怎么實現再看下文。

?

發現問題了嗎?

我們求出J2以后,按原來的做法,是該求K2的,但是K2所需要的信息和J2完全不同,紅色才是K2可能需要的信息。

所以我們以物品重量為差,先把黑色系列推出來,再推紅色系列,依此類推。

這個例子就是推三次,每組各元素之間差3.

這樣就不會出現構造一堆單調隊列的尷尬情況了。

在代碼中繼續詳細解釋:

//輸入
int n;
int W;
int w[MAX_N];
int v[MAX_N];
int m[MAX_N];

?

int dp[MAX_N+1];//壓空間,本知識參考https://blog.csdn.net/hebtu666/article/details/79964233
int deq[MAX_N+1];//雙端隊列,保存下標
int deqv[MAX_N+1];//雙端隊列,保存值

隊列存的就是所有上一行能取到的范圍,比如對于J2,隊列里存的就是G1-w[i],D1-2w[i],A1-3w[i]等等合法情況。(為了操作方便都是j,利用差實現最終的運算)

他們之中最大的就是隊頭,加上最多存儲個數就好。

?

?

?

void solve()
{for(int i=0;i<n;i++)//參考過那個網址第二題應該懂{for(int a=0;a<w[i];a++)//把每個分組都打一遍{int s=0;//初始化雙端隊列頭尾int t=0;for(int j=0;j*w[i]+a<=W;j++)//每組第j個元素{int val=dp[j*w[i]+a]-j*v[i];while(s<t && deqv[t-1]<=val)//直到不改變單調性t--;deq[t]=j;deqv[t]=val;t++;//利用隊頭求出dpdp[j*w[i]+a]=deqv[s]+j*v[i];if(deq[s]==j-m[i])s++;//檢查過期}}}
}

?

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/445564.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/445564.shtml
英文地址,請注明出處:http://en.pswp.cn/news/445564.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

用Python去除掃描型PDF中的水印

內容概述 含水印掃描型PDF文件&#xff0c;其中某頁如下圖所示&#xff0c;用Python去除其頁頂及頁底的水印。 處理思路&#xff1a;PDF中的每一頁的水印的相對位置基本相同&#xff0c;將PDF每一頁輸出成圖片&#xff0c;然后進行圖片編輯&#xff0c;用白色填充方形覆蓋水印…

鏈表實現棧

棧&#xff0c;是操作受限的線性表&#xff0c;只能在一端進行插入刪除。 其實就是帶尾指針的鏈表&#xff0c;尾插 #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define Status int #define SElemType int //只在頭部進行插入和刪除(…

二階有源濾波器

濾波器是一種使用信號通過而同時抑制無用頻率信號的電子裝置, 在信息處理、數據傳送和抑制干擾等自動控制、通信及其它電子系統中應用廣泛。濾波一般可分為有源濾波和無源濾波, 有源濾波可以使幅頻特性比較陡峭, 而無源濾波設計簡單易行, 但幅頻特性不如濾波器, 而且體積較大。…

用JS寫了一個30分鐘倒計時器

效果圖 額外功能 左鍵單擊計時器數字區&#xff0c;不顯示或顯示秒鐘區。左鍵雙擊計時器數字區&#xff0c;暫停或啟動計時器。計時完畢&#xff0c;只能刷新頁面啟動計時器。輸入框可輸入備注信息&#xff0c;輸入框失去焦點或計時完畢后&#xff0c;時間戳附帶備注信息會存入…

為什么高手離不了Linux系統?我想這就是理由!

通過本文來記錄下我在Linux系統的學習經歷&#xff0c;聊聊我為什么離不了Linux系統&#xff0c;同時也為那些想要嘗試Linux而又有所顧忌的用戶答疑解惑&#xff0c;下面將為你介紹我所喜歡的Linux系統&#xff0c;這里有一些你應該知道并為之自豪的事實。 這里你應該首先拋開W…

python學習實例(1)

# #1.2 計算機編程的基本概念 ## #1.2.2 從Python語言進入計算機語言的世界 ##<程序&#xff1a;例子1> def F(x,y):return(x*xy*y) print("F(2,2)",F(2,2)) print("F(3,2)",F(3,2))#<程序&#xff1a;例子2> def Pr():for i in range(0,10)…

用JS寫一個電影《黑客帝國》顯示屏黑底綠字雨風格的唐詩欣賞器

效果圖 放碼過來 <!DOCTYPE HTML> <html><head><meta http-equiv"Content-Type" content"text/html;charsetutf-8"/><title>Black Screen And Green Characters</title><style type"text/css">table…

python學習實例(2)

# #2.2 不同進制間的轉換 ## #2.2.1. 二進制數轉換為十進制數 ##<程序&#xff1a;2-to-10進制轉換> binput("Please enter a binary number:") d0; for i in range(0,len(b)):if b[i] 1:weight 2**(len(b)-i-1)d dweight; print(d)#<程序&#xff1a;改…

元器件封裝大全:圖解+文字詳述

先圖解如下&#xff1a; 元器件封裝類型&#xff1a; A.Axial  軸狀的封裝&#xff08;電阻的封裝&#xff09;AGP &#xff08;Accelerate raphical Port&#xff09; 加速圖形接口 AMR(Audio/MODEM Riser) 聲音/調制解調器插卡BBGA&#xff08;Ball Grid Array&#xff09;…

python學習實例(3)

# #3.4 關于Python的函數調用 ## #3.4.2 Python函數入門 ##<程序&#xff1a;計算43*22> #函數f def f(x, y):return x*y*y#主函數部分 c4f(3, 2) print (c)# #3.4.3 局部變量(Local variables)與全局變量(Global variables) ##<程序&#xff1a;打印局部變量a和全局…

用JS寫一個丐版《2048》小游戲

效果圖 放馬過來 <!DOCTYPE HTML> <html><head><meta http-equiv"Content-Type" content"text/html;charsetutf-8"/><title>2048</title><style type"text/css">.basic{height:80px;width:80px;back…

如何有效申請TI的免費樣片

轉自如何有效申請TI的免費樣片 TI公司愿意為支持中國大學的師生們的教學、實驗、創新實踐、競賽和科研項目&#xff0c;提供有限數量的免費樣片。首先需要指出的是&#xff1a;所有的樣片申請應該是誠實正當的&#xff0c;所有不恰當的申請&#xff08;包括不必要或多余的&…

python學習實例(4)

# #第四章的python程序 ## #4.1 簡潔的Python ##<程序&#xff1a;Python數組各元素加1> arr [0,1,2,3,4] for e in arr:tmpe1print (tmp)## #4.2 Python內置數據結構 ## #4.2.1 Python基本數據類型 ##<程序&#xff1a;產生10-20的隨機浮點數> import random f …

用Python批量生成字幕圖片用于視頻剪輯

說明 視頻剪輯時需要為視頻添加字幕&#xff0c;添加字幕方法之一&#xff1a;根據字幕文本文件批量生成透明底只有字幕內容的圖片文件&#xff0c;如下圖&#xff0c;然后將這些圖片文件添加到視頻剪輯軟件軌道中。 于是用pillow這Python圖片工具庫執行本次批量生成工作。 …

關于接地:數字地、模擬地、信號地、交流地、直流地、屏蔽地、浮

除了正確進行接地設計、安裝,還要正確進行各種不同信號的接地處理。控制系統中&#xff0c;大致有以下幾種地線&#xff1a; &#xff08;1&#xff09;數字地&#xff1a;也叫邏輯地&#xff0c;是各種開關量&#xff08;數字量&#xff09;信號的零電位。 &#xff08;2&…

python學習實例(5)

# #5.1 計算思維是什么 ##<程序: 找假幣的第一種方法> by Edwin Sha def findcoin_1(L):if len(L) <1:print("Error: coins are too few"); quit()i0while i<len(L):if L[i] < L[i1]: return (i)elif L[i] > L[i1]: return (i1)ii1print("All…

一個用LaTeX寫長除法計算過程的示例

源碼 \begin{array}{lr} & x1 \\ x1 \!\!\!\!\!\! & \overline{)x^2 2x 1} \\ & \underline{x^2\ \ x\ \ \ \ \ \ \ } \\ & x 1 \\ & \underline{x1} \\ & 0 \end{array}效果 x1x1???????????)x22x1 ̄x2x ̄x1x1 ̄0\begin{array}…

AltiumDesigner中PCB如何添加 Logo

AltiumDesigner中PCB如何添加 Logo 轉載2015-10-29 00:07:55標簽&#xff1a;it文化教育首先用到的畫圖軟件&#xff0c;當然是大家熟悉的Altium Designer了&#xff0c;呵呵&#xff0c;相信很多人都用過這款畫圖軟件吧&#xff08;現在電路設計一直在用&#xff09;&#xff…

python學習實例(6)

# #6.6 文件系統&#xff08;File System&#xff09; ## #6.6.3 Python中的文件操作 ##<程序&#xff1a;讀取文件os.py> f open("./Task1.txt",r); fls f.readlines() for line in fls:line line.strip(); print (line) f.close()#<程序&#xff1a;讀…

網絡視頻ts格式文件下載及將其合成單一視頻文件

一些網站會將視頻分割成n個ts文件。 用貓抓chrome插件&#xff0c;抓取index.m3u8&#xff0c;可得到眾多ts文件下載地址。 可用迅雷打包下載ts文件以及index.m3u8文件&#xff0c;但有時會出現下載不了的情況&#xff0c;懷疑是請求報頭的問題上。 若迅雷下載不了&#xff…