算法

动态规划：
定义dp[i][j]表示从前i个元素里面选择物品，当前背包剩余容量为j时能装的的最大价值
(1)第i个物品超出背包剩余容量，dp[i][j]=dp[i-1][j]
(2)第i个物品不超出背包剩余容量：
1)选择装下第i个物品：dp[i][j]=dp[i-1][j-v[i]+w[i]
1)选择不装第i个物品：dp[i][j]=dp[i-1][j]
故这种情况下dp[i][j]=max(dp[i-1][j-v[i]+w[i],dp[i-1][j])

时间复杂度

$O(n^2)$

C++ 代码

#include<iostream>
 #include<vector>
 using namespace std;

 int main()
 {
    int num,vol;
    cin>>num>>vol;

    vector<int> volumn(num+1);
    vector<int> money(num+1);
    for(int i=1;i<=num;++i)//第1个物品放在下标为1的位置
    {
        cin>>volumn[i];//体积
        cin>>money[i];//价值
    }

    vector<vector<int>> dp(num+1,vector<int>(vol+1));
    for(int i=0;i<=num;++i)
        dp[i][0]=0;//背包容量为0
    for(int j=0;j<=vol;++j)
        dp[0][j]=0;//可选择物品个数为0

    int maxValue=0;//初始化背包装的价值为0
    for(int i=1;i<=num;++i)
    {
        for(int j=1;j<=vol;++j)
        {
            if(volumn[i]<=j)
            {
                //装 、不装
                dp[i][j]=max(dp[i-1][j-volumn[i]]+money[i],dp[i-1][j]);
            }
            else
                dp[i][j]=dp[i-1][j];

            //maxValue=max(maxValue,dp[i][j]);           
        }
    }

    cout<<dp[num][vol]<<endl;
    //cout<<maxValue<<endl;
    return 0;
 }