根據上面的分析，分析出狀態和轉移方程。注意：dp 不一定只有兩維或者一維，一開始設計狀態時先不考慮維度。如果空間超了的話考慮捲動陣列等優化，或者再重新設計狀態。
可以通過哪一個條件範圍小來入手設計狀態。
對於邊界條件：一般是考慮第一個點的特殊情況，即 \(dp_{[1]}\)。
模型總結：每個物品只能選一次。
每件物品可以通過放或者不放來轉移，所以它還依賴於之前使用的容量。設 \(dp_{[i][j]}\) 表示前 \(i\) 件物品用了 \(j\) 的容量的最大價值。不難得出：\(dp_{[i][j]}=max(dp_{[i-1][j]},dp_{[i-1][j-v[i]]+w_[i]})\)。
考慮優化維度，常用的方法是優化掉前 \(i\) 個物品的維度（對很多題目也同樣適用）。設 \(dp_{[j]}\) 表示目前位置使用 \(j\) 的容量的最大價值。於是狀態轉移方程變成了：\(dp_{[j]}=max(dp_{[j]},dp_{[j-v[i]]}+w_{[i]})\)。
由於 \(v_{[i]}\ge 0\)，所以 \(j-v_{[i]}\le j\)，為了保證 \(j-v_{[i]}\) 一定是上一次 \(i-1\) 個物品的，所以我們迴圈 \(j\) 的時候要倒序迴圈。或者畫出二維 DP 轉移列表來理解。
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
模型總結：每個物品可以選無限次
按照 01 揹包的思想設計出初始狀態：設 \(dp_{[i][j]}\) 表示前 \(i\) 件物品用了 \(j\) 的容量的最大價值。然後迴圈列舉選 \(k\) 個物品，仿照上面轉移方程求出最大值。
繼續考慮優化，依舊設 \(dp_{[j]}\) 表示目前位置使用 \(j\) 的容量的最大價值。但這次不能再回圈 \(k\) 個物品了。我們返回去思考為什麼 01 揹包迴圈 \(j\) 要倒序迴圈，因為 01 揹包只能選 1 個。那麼如果它正序迴圈的話，\(dp_{[j]}\) 還有可能取到現在正在取的 \(i\) 個物品（因為 \(dp_{j-v[i]}\) 可能在這次迴圈中已經被更新過了），跟完全揹包的模型相符。
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
模型總結：每個物品有各自可選的最多次數 \(k\)。
按照完全揹包暴力的思想同樣可以得到暴力解法。
時間複雜度超時的原因主要是由於迴圈了 \(k\) 這個維度，於是接下來需要優化這個維度。這裡可以使用二進位制優化，將回圈列舉的 \(k\) 從 \([1,p]\) （\(p\) 是最多選的個數）變為 \(1,2,4...2^{k-1},p-2^k+1\)（\(k\) 是滿足 \(p-2^k+1>0\) 的最大整數）。
現在證明 \([1,p]\) 的所有數都可以被寫成上面轉化後的數的和：
對於 \(S_1=[0,(2^k-1)]\) 這一區間的數：\(2^x,2^{x-1}\) 中間相差了一個 \(2^{x-1}\)，如果 \([1,2^{x-1}-1]\) 中的所有數都可以被寫成上面的形式，那麼 \([2^{x-1},2^x]\) 中的所有數也可以滿足條件，即 \([1,2^x]\) 都會滿足條件。於是 \(x\) 的值追根溯源到 \(0\)，此時顯然 \([1,1]\) 中的所有數都會滿足條件，再根據上面的遞推就可以證明出來了。
對於 \(S_2=[2^k,p]\) 這一區間的數：\(p=(p-2^k+1)+2^k-1\)。由於這一區間內都是連續的，所以所有數都可以被表示為 \((p-2^k+1)+x\;(x\in S1)\)。證明完畢。
for(int i=1;i<=n;i++){
int maxi;
if(v[i]==0) maxi=p[i];
else maxi=min(p[i],t/v[i]);
for(int k=1;maxi>0;k<<=1){
k=min(k,maxi);
maxi-=k;
for(int j=t;j>=v[i]*k;j--) dp[j]=max(dp[j],dp[j-v[i]*k]+w[i]*k);
}
}
混合揹包：只需分類討論上述情況即可。
二維揹包費用（選一個物品有兩個價值）：只需再多增一維按照上面來轉移即可。有時另一種價值的表述方法也會變成「最多選 \(x\) 件物品」。
分組揹包（每組裡面最多選一件物品）：對每組的 \(dp_{[j]}\) 取最大即可。
依賴揹包（有些物品必需先選另一種物品後才能選）：對於每一個沒有依賴的揹包分類討論，只選它自己，選它自己+依賴1……等。
對於有些一眼能看出來的區間DP題一般都是拆分類/合併類的題，典型的有：P1880 合併石子。但關鍵要看大區間內的答案能否可以通過小區間內的答案轉移而來。
將在一段大區間內進行的DP，分解成小區間內進行的DP,大都需要以下幾個條件：
比較典型的虛擬碼：
核心思路：先計算出小區間，再推出大區間，邊界一般為區間長為 1 的時候
for 子區間長度 2 to n;
for 起點 1 to 終點不大於n
終點=起點+子區間長度-1
for 決策點 起點 to 終點-1
狀態轉移方程
對於有多種情況可以影響答案的時候，通常選擇暴力開維度來儲存資訊。但有時會導致維度太多而爆空間，這時候我們要將形式相同的維度壓縮成一維，這就是狀壓DP。
狀壓DP的一大重點便是位運算，而位運算又會引申出位元運算。下面是幾種常見位運算及位元運算的意義：
一個二進位制數位 &1 得到它本身。（& 表示兩個數的相同位上，只有兩個都為 \(1\)，最終的值才為 \(1\)。通常被看做兩個集合的交集。）
一個二進位制數位 ^1 則取反。（^ 表示兩個數的相同位上，只有值不同，最終的值才為 \(1\)）
一個二進位制數位 &0 則賦值為 \(0\)。
一個二進位制數位 |1 則賦值為 \(1\)。（| 表示兩個數的相同位上，只要有一個為 \(1\)，最終值就為 \(1\)）
(n>>k)&1 取出二進位制下 \(n\) 的第 \(k\) 位 （從右往左）。
n&((1<<k)-1) 取出二進位制下 \(n\) 的右 \(k\) 位。
n^(1<<k) 將二進位制下 \(n\) 的第 \(k\) 位取反。
n|(1<<k) 將二進位制下 \(n\) 的第 \(k\) 位賦值為 \(1\)。
n&(-(1<<k)) 將二進位制下 \(n\) 的第 \(k\) 位賦值為 \(0\)。