一、題目描述

題目來源：Acwing

有N件物品和一個容量是 V的背包。每件物品只能使用一次。第 i件物品的體積是 vi，價值是 wi。
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。輸出最大價值。

C++程序要求輸入輸出格式如下：
輸入格式
第一行兩個整數，N，V，用空格隔開，分別表示物品數量和背包容積。接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分別表示第 i件物品的體積和價值。

輸出格式
輸出一個整數，表示最大價值。

示例如下：

輸入：                    輸出：8
4 5
1 2
2 4
3 4
4 5

?

二、思路

??01背包問題是學習動態規劃的必經之路，按照之間的分析來看，依然是五個步驟：
??說明一下：a[i]表示物體i的重量，b[i]表示物體i的價值。
??1.確定dp數組的含義
??dp[i][j]表示的是前i件物品背包容量為j時的最大容量
??2.確定遞推公式
??那么可以有兩個方向推出來dp[i][j]，

• 不放物品i：由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價值，此時dp[i][j]就是dp[i -1][j]。(其實就是當物品i的重量大于背包j的重量時，物品i無法放進背包中，所以背包內的價值依然和前面相同。)
• 放物品i：由dp[i - 1][j - a[i]]推出，dp[i - 1][j - a[i]] 為背包容量為j -a[i]的時候不放物品i的最大價值，那么dp[i - 1][j - a[i]] + b[i]（物品i的價值），就是背包放物品i得到的最大價值 所以遞歸公式： dp[i][j] = max(dp[i - 1][j], dp[i -1][j - a[i]] + b[i]);

??3.dp數組的初始化

	for(int j=1;j<=V;j