首發(fā)csdn，鏈接：https://blog.csdn.net/Colicsin/article/details/115403831
問(wèn)題描述：
*現(xiàn)在給你一個(gè)容量為V的背包，有N個(gè)物品婿失，其中第i件物品的重量為wi纫版，價(jià)值為vi汇鞭，每件物品只可以拿一次耘沼，問(wèn)在有限的容量?jī)?nèi)，最多可以拿到多少價(jià)值的物品盅藻。 *
問(wèn)題分析：
對(duì)于每一個(gè)物品购桑，都有兩種策略：拿或不拿。
讀到這里氏淑，是不是腦海中有一個(gè)清晰的想法勃蜘？DFS！確實(shí)假残，這不就是我們常見的dfs問(wèn)題嗎缭贡，分別枚舉拿和不拿兩個(gè)狀態(tài)即可。于是寫下了如此代碼...
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1e6+7;
int w[MAXN],N,V,v[MAXN],book[MAXN],end=0;
void dfs(int now,int ans,int rest_v)
{
if(now>N)
{
end=max(ans,end);
return;
}
if(book[now]==false&&rest_v>=w[now])
{
ans+=v[now];
rest_v-=w[now];
book[now]=true;
dfs(now+1,ans,rest_v);
ans-=v[now];
rest_v+=w[now];
book[now]=false;
}
dfs(now+1,ans,rest_v);
}
int main()
{
cin>>V>>N;
for(int i=1;i<=N;i++)
{
cin>>w[i]>>v[i];
}
dfs(1,0,V);
cout<<end<<endl;
return 0;
}//標(biāo)準(zhǔn)的暴力dfs模板守问，遺憾30分qwq
很遺憾對(duì)于洛谷P1048的01背包模板題來(lái)說(shuō)匀归，只有30分坑资，剩下70分全部都是TLE（這是什么人間疾苦：呐痢）
不過(guò)轉(zhuǎn)念一想好像確實(shí)，我們平常dfs模板的代碼不就是解決小數(shù)據(jù)問(wèn)題的么袱贮，對(duì)于中等數(shù)據(jù)量和大數(shù)據(jù)問(wèn)題仿便，不會(huì)吧不會(huì)吧不會(huì)吧，不會(huì)真的有人想寫dfs吧？（老陰陽(yáng)怪氣了）
現(xiàn)在我們手動(dòng)模擬一下...
很顯然嗽仪，當(dāng)n特別大的時(shí)候（我覺(jué)得到100之后就已經(jīng)夠嗆了）我們的程序變得特別慢荒勇，難免TLE（原來(lái)是自己老了哈哈哈哈）
不過(guò)，車到山前必有路闻坚，我們觀察這棵橫著的遞歸樹沽翔，發(fā)現(xiàn)是不是有很多重復(fù)遍歷的部分？
比如選3窿凤，選4這個(gè)小方案仅偎，在選1，選2雳殊、選1不選2橘沥、不選1選2、不選1不選2的時(shí)候都需要訪問(wèn)一次夯秃，現(xiàn)在還只是有4個(gè)物品的情況座咆，要是有n個(gè)物品，那豈不是2^n的數(shù)量級(jí)了仓洼？實(shí)在可怕介陶，這樣一想，我們之前的代碼TLE的關(guān)鍵原因也出來(lái)了色建，就是重復(fù)遍歷的太多了斤蔓。
這時(shí)候我們就需要一個(gè)maxn_數(shù)組來(lái)輔助剪枝一下，maxn_[i][j]表示前i個(gè)物品還剩j點(diǎn)空間下能存放的物品價(jià)值的最大值镀岛，設(shè)想我們現(xiàn)在從不選1選2走到了選3選4這條路上弦牡，但是發(fā)現(xiàn)還沒(méi)走之前所選物品的值已經(jīng)比其他的路到達(dá)選3選4的路時(shí)所選的物品的值小了，那這條路我們還有必要去走嘛漂羊？Ofcourse not驾锰！所以就直接return就好咯，這樣子就完成了剪枝任務(wù)bingo走越！
如果折現(xiàn)回到代碼上椭豫，是這樣子...
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1e6+7;
int w[MAXN],N,V,v[MAXN],book[MAXN],end=0,maxn_[1001][1001];
void dfs(int now,int ans,int rest_v)
{
if(ans<=maxn_[now][rest_v])
return;
maxn_[now][rest_v]=ans;
if(now>N)
{
end=max(ans,end);
return;
}
if(book[now]==false&&rest_v>=w[now])
{
ans+=v[now];
rest_v-=w[now];
book[now]=true;
dfs(now+1,ans,rest_v);
ans-=v[now];
rest_v+=w[now];
book[now]=false;
}
dfs(now+1,ans,rest_v);
}
int main()
{
cin>>V>>N;
memset(maxn_,-1,sizeof(maxn_));
for(int i=1;i<=N;i++)
{
cin>>w[i]>>v[i];
}
dfs(1,0,V);
cout<<end<<endl;
return 0;
}//記憶化搜索AC代碼
不過(guò)比起遞歸，01背包最好的方式還是遞推旨指，這也是為什么01背包能當(dāng)作動(dòng)態(tài)規(guī)劃初步引入例題的原因了赏酥。
我們假設(shè)dp[i][j]表示前i件物品用j的容量去裝，所能達(dá)到的最大價(jià)值谆构。（是不是很熟悉裸扶？沒(méi)錯(cuò)，就是剛才記憶化搜索用到的那個(gè)判斷繼續(xù)不繼續(xù)的標(biāo)準(zhǔn)）
對(duì)于每一次決策搬素，有兩個(gè)狀態(tài)：選或不選
對(duì)于每一個(gè)狀態(tài)的值呵晨，都依賴于上一個(gè)狀態(tài)的值
滿足動(dòng)態(tài)規(guī)劃的條件√
很容易寫出狀態(tài)轉(zhuǎn)移方程：
dp[i][j]=min(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
說(shuō)得更清楚一些魏保，dp[i-1][j]不就代表這一件不選，那么就相當(dāng)于前i-1件物品放入j容量的背包的最大價(jià)值摸屠，dp[i-1][j-w[i]]代表這一件要了谓罗，前i-1件物品放入j-w[i]的容量?jī)?nèi)的最大價(jià)值。
因此我們可以寫出以下代碼....
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=1e3+7;
int w[MAXN],N,V,v[MAXN],dp[MAXN][MAXN];
int main()
{
memset(dp,0,sizeof(dp));
cin>>V>>N;
for(int i=1;i<=N;i++)
{
cin>>w[i]>>v[i];
}
for(int i=1;i<=N;i++)
{
for(int j=V;j>=0;j--)
{
if(j>=w[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
else
dp[i][j]=dp[i-1][j];
}
}
cout<<dp[N][V]<<endl;
return 0;
}//二維數(shù)組AC代碼
但是事情就到這里就結(jié)束了嗎季二？當(dāng)然沒(méi)有檩咱！
沒(méi)錯(cuò)，還可以接著優(yōu)化胯舷！時(shí)間優(yōu)化税手？并不，空間優(yōu)化需纳。畢竟二維數(shù)組還是很坑的芦倒，萬(wàn)一比賽碰到了一些“善良的死神”，直接MLE了....
從上面我們分析注意到不翩，每一層i的狀態(tài)都和上一層i-1的狀態(tài)有關(guān)兵扬，這樣子我們是不是并不需要開二維數(shù)組呢？這個(gè)時(shí)候口蝠，滾動(dòng)數(shù)組閃亮出場(chǎng)~
啥是滾動(dòng)數(shù)組器钟？這還要從頭憶起，說(shuō)簡(jiǎn)單點(diǎn)妙蔗，滾動(dòng)數(shù)組就是一個(gè)很小的數(shù)組傲霸，一直滾...一直滾...好吧其實(shí)就是不斷更新的數(shù)組。
這里用斐波那契數(shù)列來(lái)舉例子確實(shí)再好不過(guò)眉反，因?yàn)殪巢瞧鯏?shù)列第i項(xiàng)就是前兩項(xiàng)之和昙啄，所以對(duì)于斐波那契數(shù)列來(lái)說(shuō)，有以下代碼...
f[1]=1;
f[2]=1;
for(int i=2;i<=n;i++)
{
f[0]=f[1];
f[1]=f[2];
f[2]=f[0]+f[1];
}
這樣子最后f[n]就是第n項(xiàng)的值咯~
從滾動(dòng)數(shù)組得到經(jīng)驗(yàn)寸五，我們用滾動(dòng)數(shù)組來(lái)優(yōu)化我們的二維dp代碼...
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=1e3+7;
int w[MAXN],N,V,v[MAXN],dp[100001];
int main()
{
memset(dp,0,sizeof(dp));
cin>>V>>N;
for(int i=1;i<=N;i++)
{
cin>>w[i]>>v[i];
}
for(int i=1;i<=N;i++)
{
for(int j=V;j>=0;j--)
{
if(j>=w[i])
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[V]<<endl;
return 0;
}//一維數(shù)組AC代碼
Ps：對(duì)于一維數(shù)組梳凛，j循環(huán)必須要倒序遍歷，為了防止多重迭代現(xiàn)象梳杏；
舉個(gè)小例子韧拒；
假設(shè)給定數(shù)據(jù)：
10 3
5 5
8 7
4 6
剛開始數(shù)組dp內(nèi)都是初始化為0，因?yàn)闆](méi)有裝入任何東西
第一遍遍歷十性，從前往后
第二遍遍歷叛溢，從前往后
第三次遍歷，從前往后
很顯然劲适，出現(xiàn)了什么情況呢楷掉？居然最大到了17，這里我們可以看到减响，根據(jù)狀態(tài)轉(zhuǎn)移方程式dp[j]=max(dp[j],dp[j-w[i]]+v[i])來(lái)看靖诗，在第三次遍歷（i=3），還未遍歷時(shí)dp[8]=7支示。開始遍歷之后刊橘，dp[8]=max(dp[8],dp[4]+v[3])，這個(gè)時(shí)候發(fā)現(xiàn)肯定是dp[4]+v[3]更大一些颂鸿，但是這個(gè)時(shí)候要注意促绵，dp[4]是已經(jīng)拿完了第三件物品的，按理來(lái)說(shuō)嘴纺，我們并沒(méi)有辦法再去拿第三件物品了败晴，因?yàn)槊恳粋€(gè)物品只能拿一件，所以就行不通咯栽渴，自然就不可以用正序的方法尖坤。而倒序的方法則是先盡可能地都拿著，在最大化的前提下去判斷闲擦，自然是可以的慢味。
01背包問(wèn)題就到此完結(jié)
