题目描述

include [HTML_REMOVED]

using namespace std;

// 01背包
const int N = 1010;
int n,m;
int dp[N]; //表示dp[n][m] 前n个物品当体积为v时的最大总价值数
int w[N],v[N];

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
}

for(int i=1;i<=n;i++){
    // dp方程 dp[i,j] = max dp[i-1][j] dp[i-1][j-v[i]]+w[i];
    for(int j=m;j>=v[i];j--){
        // 不考虑第i个
        // dp[i][j] = dp[i-1][j];  去掉第一层仍然是相等的
        // dp[j] = dp[j]
        // if(j>=v[i]){
            // 考虑
            //dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
            // 由于为了保证dp[j-v[i]] = dp[i-1][j-v[i]] 因此要保证第i层时j-vi是第i-1层的
            // 因此从后向前，此时在算j时，j-vi是第i-1层
            dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
        // }
    }
}
cout << dp[m];

}

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla