學習者不靈絲相傳，而自杖明月相反，子來此事卻無得失。
前言
盡管計算機是門嚴謹?shù)膶W科，但正因為嚴謹，所以要有趣味才能看得下去。在筆者的前幾篇算法類文章中，都采用了以小故事作為引入的方式來介紹算法，但在回看的時候發(fā)現(xiàn)學術味還是太濃了，完全沒有想看下去的欲望orz~因此筆者決定改組文章結構，將整個算法都以故事的形式呈現(xiàn)，至少讓讀者能看下去，希望能幫助到大家！
正文
小明的探險之旅（2）
上文說到小明從家中收拾好裝備后，就踏上了茫茫星海的探險征程。在航行了數(shù)天后，他到達了第一個星球——食戟之星。這顆星球以昂貴而美味的食物而著稱，由于小明實在太餓，他直接鉆進了一家自助餐店，想好好的回回血。
小明看著這些食物不禁直流口水：這么多好吃的，都好想吃！可是怎么吃才能吃的最好呢。。（注：小明吃好的標準是吃到的所有食物價格總和最高，也就是最能回本）
（小明思考了一會）
小明：感覺這個問題和我搬裝備時候的問題很像，但是這次所有食物都是無限供應的。。先想一想之前用到的轉移方程吧！
那么，之前的裝備一種只有一件，而這次的食物有無數(shù)件，也就是說，不一定是j-w[i]，也可以是j-2w[i]，j-3w[i]……所以就是
可是這樣的話，時間復雜度就太大了……就算用了滾動數(shù)組優(yōu)化，也會到達平方級的時間復雜度，還要進行復雜的邊界判斷……
（小明陷入了苦想，直覺告訴他，這種算法還可以進行優(yōu)化，但以他的學識，想破腦袋也想不出來。最后，小明只能按照這種算法不停推算，等到推算完，他撐著饑腸轆轆的身體去取餐的時候，卻發(fā)現(xiàn)已經(jīng)到了打烊的時間了！小明沒辦法，只能到街上買了一個手抓餅，一邊淚流滿面的吃著，一邊發(fā)誓自己一定要學好算法……）
最后的優(yōu)化
實際上，小明的直覺很準確，可惜他的智商沒有直覺那么強大~那么接下來，我們接手他的思路，看看接下來還有什么能優(yōu)化的地方。
很顯然，這次依然可以用滾動數(shù)組優(yōu)化，但為了展示方便，我們先壓縮到i和i-1兩行：
黃色塊是我們當前要確定的值，即fi,j紅色塊是根據(jù)上面的公式，我們枚舉的值，設w[i]=2，則：
接下來是重點，我們看確定fi,j-2時的表格，黃色塊是要確定的值，紅色塊是枚舉的值：
發(fā)現(xiàn)了什么？fi,j-2的值其實就是除了fi-1,j之外的所有紅色塊的最大值，那么我們可以通過只比較fi,j-2和fi-1,j這兩個塊的值就可以得出fi,j的值了，即：
這就是完全背包問題的轉移方程。接下來上代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-419004.html
代碼
#include <iostream>
using namespace std;
const int maxn = 13010;
int n, W, w[maxn], v[maxn], f[maxn];
int main() {
cin >> n >> W;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++)//循環(huán)n次，因為要對n件物品進行選擇
for (int l = w[i]; l <= W; l++)//從前向后更新
f[l] = max(f[l], f[l - w[i]] + v[i]);//轉移方程
cout << f[W];
return 0;
最后小記以下筆者在寫這篇博客時想到的一個關于邊界處理的問題：當l<w[i]時，不可能再取第i件物品，所以不會改變數(shù)組中的數(shù)據(jù)；而一開始由于定義的是全局變量，所以數(shù)據(jù)都初始化為0，也與如果一直不取物品的話，價值為0的事實相符合，所以不特意處理邊界是沒問題的。
我是霜_哀，在算法之路上努力前行的一位萌新，感謝你的閱讀！碼文不易，如果覺得好的話，可以關注一下，我會在將來帶來更多更全面的算法講解！文章來源地址http://www.zghlxwxcb.cn/news/detail-419004.html
到了這里，關于【算法宇宙——在故事中學算法】背包dp之完全背包問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
