代码随想录算法训练营第四十天|卡码网46 携带研究材料、

46.携带研究材料

���路：0-1背包问题。确定dp数组及其下标的含义。dp[i][j]表示向空间大小为j的背包里放0~i个物品的最大价值。递推公式dp[i][j] = max(dp[i-1][j],dp[i-1][j-space[i]]+value[i])，有两种情况，不放i进背包，放i进背包，放i进背包的话，背包至少为i空余处space[i]的位置。初始化dp数组，dp[i][0]=0，因为背包容量为0时，什么都放不进去，价值为0。dp[0][i] = value[i] i>=space[i]。当背包容量大于第一个物品的容量时价值为第一个物品的价值。当前位置的价值只与上左方向位置的价值有关，因此遍历顺序为从左到右从上到下。打印dp数组，可以用于debug。

#include
using namespace std;
#include
int maxvalue(vector& space,vector& value,int N,int M)
{
    //确定dp数组及其下标的含义 dp[i][j]代表0~i号物品放入空间j的最大价值
    //递推公式 dp[i][j] = max( dp[i-1][j],dp[i-1][j-space[i]]+value[i]);
    //初始化dp数组 dp[i][0] = 0; dp[0][j] = value[0]; j>=space[0];
    //遍历顺序 从左到右 从上到下 当前值取决于左上值
    //打印dp数组，用于debug
    vector dp(M,vector(N+1,0));
    for(int j = space[0];jN;
    vector space(M);
    vector value(M);
    for(int i =0;i>space[i];
    }
    for(int i = 0;i>value[i];
    }
    cout