01背包

for(int i=0;i<n;i++) //遍歷每一件物品for(int j=v;j>=wei[i];j--)//遍歷背包容量，表示在上一層的基礎上，容量為J時，第i件物品裝或不裝的最優解;dp[j]=max(dp[j-wei[i]]+val[i],dp[j])；

初始化細節：裝滿dp[0]=0;其余賦值-INF；不裝滿全初始化為0；

完全背包

for(int i=0;i<n;i++) //遍歷每一類物品for(int j=wei[i];j<=v;j++)//遍歷容量，此時代表第一類物品選了幾件。與0/1區別正序遍歷dp[j]=max(dp[j-wei[i]]+val[i],dp[j])；

多重背包

for(int i=0;i<n;i++) //遍歷每一個物品 for(int j=0;j<=num[i];j++) //遍歷物品的數量 for(int k=m;k>=weight[i];k--) //當做01背包來處理 { //取01背包情況的dp[k]和dp[k-weight[i]]+value[i]的最大值 dp[k]=max( dp[k],dp[k-weight[i]]+value[i] ）;}

二進制優化
優化原因：

多重背包轉換成 01 背包問題就是多了個初始化，把它的件數C 用
分解成若干個件數的集合，這里面數字可以組合成任意小于等于C
的件數，而且不會重復，之所以叫二進制分解，是因為這樣分解可
以用數字的二進制形式來解釋
比如：7的二進制 7 = 111 它可以分解成 001 010 100 這三個數可以
組合成任意小于等于7 的數，而且每種組合都會得到不同的數
15 = 1111 可分解成 0001 0010 0100 1000 四個數字
如果13 = 1101 則分解為 0001 0010 0100 0110 前三個數字可以組合成
7以內任意一個數，加上 0110 = 6 可以組合成任意一個大于6 小于13
的數，雖然有重復但總是能把 13 以內所有的數都考慮到了，基于這種
思想去把多件物品轉換為，多種一件物品，就可用01 背包求解了。

for(int i=0;i<n;i++) {cin>>w[i]>>v[i]>>c[i];//對每一種類的c[i]件物品進行二進制分解for(int j=1;j<=c[i];j<<=1){ //右移=*2 value[cnt]=j*v[i];weight[cnt]=j*w[i];cnt++;c[i]-=j; } if(c[i]>0){alue[cnt]=c[i]*v[i];weight[cnt]=c[i]*w[i];cnt++;} } 01背包求解.....

好像單調隊列也能優化，多重背包；
下一期整理

總結

以上是生活随笔為你收集整理的DP背包（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。