代码随想录算法训练营第四十天|卡码网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。

#includeusing namespace std;#includeint 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