完全背包問題(動态規劃）

3. 完全背包問題

•    題目
•    送出記錄
•    讨論
•    題解
•    視訊講解

有 NN 種物品和一個容量是 VV 的背包，每種物品都有無限件可用。

第 ii 種物品的體積是 vivi，價值是 wiwi。

求解将哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。

輸出最大價值。

輸入格式

第一行兩個整數，N，VN，V，用空格隔開，分别表示物品種數和背包容積。

接下來有 NN 行，每行兩個整數 vi,wivi,wi，用空格隔開，分别表示第 ii 種物品的體積和價值。

輸出格式

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

資料範圍

0<N,V≤10000<N,V≤1000

0<vi,wi≤10000<vi,wi≤1000

輸入樣例

4 5
1 2
2 4
3 4
4 5
           

輸出樣例：

10
           

完全背包問題與01背包問題是不一樣的，對于01背包，每個物品隻有兩個選擇，不要，或者拿一個，是以對于dp[i][j](在容量為J時，拿第I個物品時的總價值)它的最大值要不是dp[i-1][j]，不拿,要不就是dp[i][j-v[i]]+w[i]],拿

但是對于完全背包，并不是這麼簡單它可以拿很多個是以它的狀态轉移方程是

dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]+w[i],dp[i-1][j-2*v[i]]+2*w[i]]......dp[i-1][j-k*v[i]]+k*w[i])隻要J能夠滿足容量,而我們可得到另一個數組的公式

dp[i][j-v]=max(dp[i-1][j-v],dp[i-1][j-2*v]+w[i]......)  它與上述公式max判斷的第二位僅僅差一個w,是以max的第二位可以轉化為

dp[i][j-v]+w[i];這樣就可以得到簡化的狀态轉移方程，那麼完全背包就很容易寫出來來了

我寫的完全背包還沒有優化數組，就是二維優化為一維，但是也不是很難了，

#include<bits/stdc++.h>
using namespace std;
int w[10001],v[10001];
int dp[10010][10010];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=v[i])
                dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
        }
    }
    cout<<dp[n][m];
}