1.1 題目

有 N 件物品和一個(gè)容量為 V 的背包。放入第 i 件物品耗費(fèi)的費(fèi)用是 Ci1，得到的
價(jià)值是 Wi。求解將哪些物品裝入背包可使價(jià)值總和最大。

1.2 基本思路

這是最基礎(chǔ)的背包問(wèn)題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。
用子問(wèn)題定義狀態(tài)：即 F [i; v] 表示前 i 件物品恰放入一個(gè)容量為 v 的背包可以獲得
的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：

F[i,v] = max{F[i-1,v],F[i-1,v-Ci]+Wi}

這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的。所
以有必要將它詳細(xì)解釋一下：“將前 i 件物品放入容量為 v 的背包中”這個(gè)子問(wèn)題，若只考慮第 i 件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只和前 i ? 1 件物品相關(guān)
的問(wèn)題。如果不放第 i 件物品，那么問(wèn)題就轉(zhuǎn)化為“前 i ? 1 件物品放入容量為 v 的背
包中”，價(jià)值為 F [i ? 1; v]；如果放第 i 件物品，那么問(wèn)題就轉(zhuǎn)化為“前 i ? 1 件物品放
入剩下的容量為 v ? Ci 的背包中”，此時(shí)能獲得的最大價(jià)值就是 F [i ? 1; v ? Ci] 再加上
通過(guò)放入第 i 件物品獲得的價(jià)值 Wi。
代碼如下：

image.png

優(yōu)化：
發(fā)現(xiàn)這個(gè)二維數(shù)組可以用一維數(shù)組表示，由于有些值只用過(guò)一次沒(méi)有必要保存

于是就寫(xiě)出了這個(gè)

for(i=1;i<=n;i++)

      for(j=w[i];j<=m;j++)

       dp[j]=max{dp[j],dp[j-w[i]]+v[i]};

但是注意到上面二維的代碼中dp[i]是由dp[i-1]推出的，如果直接改成一維的就會(huì)出現(xiàn)重復(fù)選擇物品的現(xiàn)象，即：dp[j] = max{dp[j],dp[i][j-w[i]]+v[i]};

這是因?yàn)樵趈從小到大遍歷時(shí)，出現(xiàn)dp[i][j-w[i]]比dp[i][j]更先遍歷得到值;而dp[i][j-w[i]]已經(jīng)選擇過(guò)了第i個(gè)元素。因此，這么做重復(fù)選擇了i。變成了完全背包問(wèn)題。逆序推使得更小的索引更后遍歷。能夠保證 dp[j-c[i]] 保存的是狀態(tài)是 dp[i-1][j-c[i]] ，也就是每個(gè)物品只被使用了一次；順序的話 dp[j-w[i]] 保存的是 dp[i][j-w[i]] ，每個(gè)物品有可能被使用多次，也就是完全背包問(wèn)題的解法。
將代碼改成：

for(i=1;i<=n;i++)

      for(j=m;j>=w[i];j--)

       dp[j]=max{dp[j],dp[j-w[i]]+v[i]};

例題：
https://leetcode-cn.com/problems/ones-and-zeroes/

474. 一和零

難度中等284

給你一個(gè)二進(jìn)制字符串?dāng)?shù)組 strs 和兩個(gè)整數(shù) m 和 n 。

請(qǐng)你找出并返回 strs 的最大子集的大小，該子集中 最多 有 m 個(gè) 0 和 n 個(gè) 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

輸入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
輸出：4
解釋：最多有 5 個(gè) 0 和 3 個(gè) 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他滿足題意但較小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不滿足題意，因?yàn)樗?4 個(gè) 1 ，大于 n 的值 3 。
</pre>

示例 2：

輸入：strs = ["10", "0", "1"], m = 1, n = 1
輸出：2
解釋：最大的子集是 {"0", "1"} ，所以答案是 2 。
</pre>

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 僅由 '0' 和 '1' 組成
• 1 <= m, n <= 100

代碼：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // 能取幾個(gè);
        // dp[i][j][k] 表示：第0~i個(gè)物品，j個(gè)0，K個(gè)1的限制，最多能取幾個(gè);
        int[][] dp = new int[m+1][n+1];
        if(strs.length==0){return 0;}
        for(int i=0;i<strs.length;i++){
            int numsZero = 0;
            for(int l=0;l<strs[i].length();l++){
                if(strs[i].charAt(l)=='0'){
                    numsZero++;
                }
            }
            int numsOne = strs[i].length() - numsZero;
            for(int j=m;j>=numsZero;j--){
                for(int k=n;k>=numsOne;k--){
                    dp[j][k] = Math.max(dp[j][k],dp[j-numsZero][k-numsOne]+1);
                }
            }
        }
        return dp[m][n];
    }
}