背包问题的外围公式

把每个背包问题的外围代码放在一块，更好的辨别不同问题的代码实现。当然，在实现代码之前，要先理解每个背包问题解决问题的思路。

物品的分量数组是 weight (int[])，价值数组是 value (int[])，背包容量是 bagWeight

1. 0-1 背包

从大到小遍历，为了保障每个物品仅被增加一次

1.1 应用二维数组存储

递推公式

dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])
(dp[i][j]：放入物品和不放入物品，哪个值大 )

dp 大小

int[weight.size()][bagWeight+1]（[物品个数][背包容量 +1]）

代码

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) {for(int j = bagWeight; j >= 0; 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])
    }
}

1.2 应用一维数组存储

递推公式

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
(dp[j]：放入物品和不放入物品，哪个值大 )

dp 大小

int[bagWeight+1]（[背包容量 +1]）

代码

// 先遍历物品，再遍历背包
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]);
    }
}

2. 齐全背包

齐全背包的物品是能够增加屡次的，所以要从小到大去遍历

2.1 组合

递推公式

dp[j] = max(dp[j], dp[j-nums[i]]) (dp[j]：由 dp[1], dp[2], ... dp[j-1] 而来 )

递推公式依据理论状况有所变动，通过找寻 dp[j] 是怎么通过其余的 dp 值推导而确定公式

dp 大小

int[bagWeight+1]（[背包容量 +1]）

代码

// 先遍历物品，再遍历背包
for (int i = 0; i < weight.size(); i++) {for(int j = weight[i]; j < bagWeight ; j++) {dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
    }
}

2.2 排列

递推公式

dp[j] = dp[j-nums[i]] (dp[j]：由 dp[1], dp[2] ... dp[j-1] 而来 )

递推公式依据理论状况有所变动，通过找寻 dp[j] 是怎么通过其余的 dp 值推导而确定公式

dp 大小

int[bagWeight+1]（[背包容量 +1]）

代码

// 先遍历背包，再遍历物品
for(int j = 0; j <= bagWeight; j++) {for(int i = 0; i < weight.size(); i++) {if (j >= wieght[i]) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}