// 全局變量用於記錄最大價值
int maxValue = 0;
// 物品的重量和價值數組
vector weights = {1, 3, 4, 5, 6};
vector values = {1, 3, 4, 5, 6};
// 揹包容量
int capacity = 10;
// 回溯函數
void backtrack(int index, int currentWeight, int currentValue) {
    // 如果已經遍歷完所有物品
    if (index == weights.size()) {
        // 更新最大價值
        if (currentValue > maxValue) {
            maxValue = currentValue;
        }
        return;
    }
    // 不選擇當前物品 - 01揹包中的0
    backtrack(index + 1, currentWeight, currentValue);
    // 選擇當前物品   - 01揹包中的1
    if (currentWeight + weights[index] <= capacity) {
        backtrack(index + 1, currentWeight + weights[index], currentValue + values[index]);
    }
}

dp[i][j]表示將前i件物品裝進限重為j的揹包可以獲得的最大價值, 0<=i<=N, 0<=j<=W

dp[weight.size()][bagweight + 1];
// weight數組的大小 就是物品個數
for(int i = 1; i < weight.size(); i++) { // 遍歷物品
    for(int j = 0; j <= bagweight; j++) { // 遍歷揹包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

for(int i = 0; i < weight.size(); ++i){
    for(int j = bagWeight; j>=weight[i]; j--){
        dp[j] = max( dp[j], dp[j-weight[i]]+value[i] );
    }
}

class Solution {
    // 最大也就意味着最接近
    // 能通過動態規劃解決的，都能通過回溯解決
    // 每個數字都有兩種狀態，被選中，或者不被選中
    // 只有單純的數字，那麼數字的大小是重量，也是價值。
public:
    bool canPartition(vector& nums) {
        int cur = 0;
        for(int i:nums) cur+=i;
        int sum = cur/2;
        if(sum*2 != cur) return false; // 意外情況，直接排除
        vector dp(sum+1,0);
        for(int i=0; i=nums[i]; --j){
                dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }
        return sum==dp[sum]?true:false;
    }
};();>

class Solution {
    // 對吶，只要讓兩撥石頭血拼就行！
    // 但是，為啥要讓兩撥石頭血拼？
    // 圖片上附上解析，希望以後能看懂
public:
    int lastStoneWeightII(vector& stones) {
        int sum = 0;
        for(int i : stones) sum+=i;
        int cur = sum;
        sum>>=1; // 右移2位，相當於除以2；
        vector dp(sum+1, 0);
        for(int i=0; i=stones[i]; --j){
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return cur-2*dp[sum];
    }
};();>

class Solution {
    // 如果用暴力解法，本題也是能做的
    // 但是如果我不暴力呢？
    // 瞭解過答案之後，就發現這道題目，純純是一道推理題。
    // 用方法就行推理，真tm是一道推理題
    // (cur+)+(cur-) = target;
    // (cur+)-(cur-) = target;
    //  cur = (sum-target)/2; 由此公式推導
    // 只要找到cur就OK了
    // 當sum為0時，代表總和與target相同，都只有一種情況
public:
    int findTargetSumWays(vector& nums, int target) {
        int cur = 0;
        for(int i:nums) cur+=i;
        int sum = (cur-target)>>1;
        if(sum*2!=cur-target||sum<0) return 0; // 直接就沒有可能了
        vector dp(sum+1);
        dp[0]=1;
        // 公式推導出來的正整數
        for(int i=0; i=nums[i]; --j){
                dp[j]=dp[j-nums[i]]+dp[j];
            }
        }
        return dp[sum];
    }
};
// ???我的腦袋裏，有個大大的問題？這能過？？();>

class Solution {
    // 直接就幹到n的三次方了！我的天吶，太牛了
public:
    int findMaxForm(vector& strs, int m, int n) {
        vector> dp(m+1,vector(n+1,0));
        for(string str : strs){
            int num0=0,num1=0;
            for(char c : str){
                if(c=='0') num0++;
                else num1++;
            }
            for(int i=m; i>=num0; --i){
                for(int j=n; j>=num1; --j){
                    dp[i][j] = max(dp[i][j],dp[i-num0][j-num1]+1);
                }
            }
        }
        return dp[m][n];
    }
};