動態規劃 01揹包問題

2022-11-24 17:41:15 字數 2047 閱讀 4017

今天小編閒的不行,就開啟洛谷,隨便一打卡就是大吉,還宜刷題。

正巧上午比賽時有一道揹包問題,於是小編默默開啟試煉場,瞅準了揹包問題(別問我為什麼),正所謂自知者明,小編也知道自己很水(建議看揹包九講),於是挑了三道題:

在寫之前總得知道什麼是揹包問題吧,揹包問題一般長這樣:

題目:有n件物品和一個容量為v的揹包。第i件物品的費用是w[i],價值是value[i]。求解將哪些物品裝入揹包可使價值總和最大。

那麼如何解這種題目呢,先定義一個陣列f[i][j]為當一共有i件物品,揹包容量為j時的最大價值。然後就要找狀態轉移方程了,小編以前總認為狀態轉移方程難寫,但是隻要一項一項列出來就好了。對於每一個物品,無非就兩種可能:要麼選,要麼不選。那麼先看選,凡是總有回報和代價把,選了之後代價是什麼呢?想一想,是不是選了之後揹包剩餘容量就減少了;那麼回報呢?當然是價值增加了唄。但是不選就不一樣了,應為啥也沒幹,最大價值和之前一樣,不增不減。這不就出來了嘛,兩種情況如下:

因為題目求的是最大價值,所以兩者中取大的就可以了,得到以下狀態轉移方程:

f[i][j]=max(f[i-1][j-w[i]]+value[i],f[i-1][j]);

有沒有發現什麼,我們用了二維陣列,雖然時間上已經難以優化,但是空間上還是可以優化成一維陣列的,只要同時去掉i的那一個維度就可以了,因為二維陣列有太多不需要一直記錄的,直接不斷更新一維陣列(滾動陣列的方式)就可以了,更改如下:

f[j]=max(f[j-w[i]]+value[i],f[j]);

具體怎麼實現,看幾道吧。

先看第一道:

這道題處於秒殺的行列,直接用剛才的方法,把錢數看成是容量,把重要程度***看成是價值就好了,直接寫就行,**奉上:

1 #include2

using

namespace

std;

3long

long cost[30000],w[30000],f[30000

],ans;

4int

main()

516 cout<

17return0;

18 }

先來看一下采藥,比上面的還簡單:

把時間看成容量,就可以了,**獻上:

1 #include2

using

namespace

std;

3int t,m,w[1000],cost[1000],f[1000];4

intmain()

514 cout<

1516

return0;

17 }

最後來看小a點菜:

這道題乍一看沒思路,還按照剛才的思路:要麼吃,要麼不吃,吃有什麼代價,什麼回報呢?錢變少了,方案數變多了唄;不吃呢?還是原來的方案數。這樣兩種情況就出來了:

【注意】情況有變,這一次就不那麼簡單了,因為選和不選是兩種不同的方案數,題目求的是一共的方案數,所以不是max,不是min,而是+。

歸根結底長這樣:f[j]=f[j]+f[j-cost[i]];

這樣**就出來了,**呈上:

1 #include2

using

namespace

std;

3int n,m,cost[100000],f[10000];4

intmain()

5