想了解更多資料結構以及算法題，可以關注微信公衆号“資料結構和算法”，每天一題為你精彩解答。也可以掃描下面的二維碼關注
描述
背包問題是動态規劃中最經典的一道算法題。背包問題的種類比較多，我們先來看一個最簡單的背包問題-基礎背包。他是這樣描述的。
有N件物品和一個容量為V的包，第i件物品的重量是w[i]，價值是v[i]，求将哪些物品裝入背包可使這些物品的重量總和不能超過背包容量，且價值總和最大。我們先來舉個例子分析一下
舉例分析
假設我們背包可容納的重量是4kg，有3樣東西可供我們選擇，一個是高壓鍋有4kg，價值300元，一個是風扇有3kg，價值200元，最後一個是一雙運動鞋有1kg，價值150元。問要裝哪些東西在重量不能超過背包容量的情況下價值最大。如果隻裝高壓鍋價值才300元，如果裝風扇和運動鞋價值将達到350元，是以裝風扇和運動鞋才是最優解，我們來畫個圖分析一下
我們上面選擇的順序是：運動鞋→高壓鍋→風扇，如果我們改變選擇的順序，結果會不會改變，比如我們選擇的順序是：風扇→運動鞋→高壓鍋，我們還是來畫個圖看一下
我們發現無論選擇順序怎麼改變都不會改變最終的結果。
資料測試：
public static void main(String[] args) {
System.out.println("最終結果是：" + packageProblem1());
}
public static int packageProblem1() {
int packageContainWeight = 4;//包最大可裝重量
int[] weight = {1, 4, 3};//3個物品的重量
int[] value = {150, 300, 200};//3個物品的價值
int[][] dp = new int[weight.length + 1][packageContainWeight + 1];
for (int i = 1; i <= value.length; i++) {
for (int j = 1; j <= packageContainWeight; j++) {
if (j >= weight[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
Util.printTwoIntArrays(dp);//這一行僅做列印觀測資料，也可以去掉
return dp[weight.length][packageContainWeight];
}
運作結果
和我們上面分析的完全一緻。（為了測試友善，這裡的所有資料我都是寫死的，我們也可以把這些資料提取出來，作為函數參數傳進來。)
空間優化：
其實這題還可以優化一下，這裡的二維數組我們每次計算的時候都是隻需要上一行的數字，其他的我們都用不到，是以我們可以用一維空間的數組來記錄上一行的值即可，但要記住一維的時候一定要逆序，否則會導緻重複計算。我們來看下代碼
public static int packageProblem2() {
int packageContainWeight = 4;
int[] weight = {1, 4, 3};
int[] value = {150, 300, 200};
int[] dp = new int[packageContainWeight + 1];
for (int i = 1; i <= value.length; i++) {
for (int j = packageContainWeight; j >= 1; j--) {
if (j - weight[i - 1] >= 0)
dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
}
Util.printIntArrays(dp);
System.out.println();
}
return dp[packageContainWeight];
}
注意：
我們看到第7行在周遊重量的時候采用的是逆序的方式，因為第9行在計算dp[j]的值的時候，數組後面的值會依賴前面的值，而前面的值不會依賴後面的值，如果不采用逆序的方式，數組前面的值更新了會對後面産生影響。
運作結果
C++：
#include<iostream>
#include <algorithm>
using namespace std;
int main()
{
int weight[] = { 1,4,3 };
int value[] = {150, 300, 200 };
int packageContainWeight = 4;
int dp[4][5]= { { 0 } };
for (int i = 1; i <4 ; i++)
{
for (int j = 1; j < 5; j++)
{
if (j >= weight[i - 1])
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
else
dp[i][j] = dp[i - 1][j];
}
}
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 5; j++)
{
cout << dp[i][j] << ' ';
}
cout << endl;
}
return 0;
}
運作結果
遞歸寫法：
除了上面的兩種寫法以外，我們還可以使用遞歸的方式，代碼中有注釋，有興趣的可以自己看，就不在詳細介紹。
int[] weight = {1, 4, 3};//3個物品的重量
int[] value = {150, 300, 200};//3個物品的價值
// i：處理到第i件物品，j可容納的重量
public int packageProblem3(int i, int j) {
if (i == -1)
return 0;
int v1 = 0;
if (j >= weight[i]) {//如果剩餘空間大于所放的物品
v1 = packageProblem3(i - 1, j - weight[i]) + value[i]; //選第i件
}
int v2 = packageProblem3(i - 1, j);//不選第i件
return Math.max(v1, v2);
}