通过网站如何做海外贸易,做网站没什么用啊老师别人强,企业登记信息查询,怎样向网站上传照片背包问题
二维
46. 携带研究材料#xff08;第六期模拟笔试#xff09; (kamacoder.com)
dp数组有两维#xff0c;横轴表示背包重量j#xff08;0-j#xff09;#xff0c;纵轴表示不同物品#xff08;0-i#xff09;#xff0c;dp[i][j]即表示从下标为[0-i]的物品…背包问题
二维
46. 携带研究材料第六期模拟笔试 (kamacoder.com)
dp数组有两维横轴表示背包重量j0-j纵轴表示不同物品0-idp[i][j]即表示从下标为[0-i]的物品里任意取对于重量为j的背包最大的价值是多少。dp[i][j]的对物品i来说只有2种情况物品i未放入或者放入如果物品i未放入由dp[i-1][j]可以推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i-1][j]当物品i的重量大于背包j的重量时物品i无法放进背包中所以背包内的价值依然和前面相同。参考代码随想录 (programmercarl.com)放物品时
dp[i][j] dp[i-1][j-weight[i]]value[i]即当未放入i时且重量为j-weight[i]的dp值加上i的价值。
即dp[i][j]的最终推导公式为dp[i][j] max(dp[i-1][j],dp[i-1][j-weight[i]]value[i])
考虑到dp[i][j]的含义则dp[i][0]意味着背包重量为0的价值理应全为0dp[i][0]的值初始化全部为0,此外当i为0时若jweight[0]时dp[i][j]的值应该为0因为背包容量比编号为0的物品重量要小而当jweight[0]时dp[0][j]的值应该是value[0]因为背包容量足够放编号为0的物品注意这里是0-1背包问题只有放入和取出两种操作所以这里dp[0][j]只为values[0]而不是values[0]的倍数
由于dp的递推公式dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])当前dp[i][j]仅与之前的元素有关其他地方无需初始化。
vectorvectorintdp(weight.size(),vectorint(bagweight 1, 0));
for(int j weight[0]; j bagweight; j){dp[0][j] value[0];
}
之后是确定遍历顺序对物品和背包的遍历都是可行的。
以遍历物品为例当jweight[i]时无法将物品i放入则dp[i][j] dp[i-1][j]否则为上述的dp公式。
for(int i 1; i weight.size();i){for(int j 0; j bagweight; j ){if(j weight[i])dp[i][j] dp[i-1][j];elsedp[i][j] max(dp[i][j-1],dp[i-1][j-weight[i]]value[i]);}
}
遍历背包的话
for(int j 0; j bagweight; j){for(int i 0; i weight.size(); i){if(j weight[i])dp[i][j] dp[i-1][j];elsedp[i][j] max(dp[i-1][j],dp[i-1][j-value[i]] value[i]);}
}
只是变更一下顺序其他一样对本题是这样的。
之后就是返回dp数组的最大值即可。
代码随想录的代码如下
//二维dp数组实现
#include bits/stdc.h
using namespace std;int n, bagweight;// bagweight代表行李箱空间
void solve() {vectorint weight(n, 0); // 存储每件物品所占空间vectorint value(n, 0); // 存储每件物品价值for(int i 0; i n; i) {cin weight[i];}for(int j 0; j n; j) {cin value[j];}// dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值vectorvectorint dp(weight.size(), vectorint(bagweight 1, 0));// 初始化, 因为需要用到dp[i - 1]的值// j weight[0]已在上方被初始化为0// j weight[0]的值就初始化为value[0]for (int j weight[0]; j bagweight; j) {dp[0][j] value[0];}for(int i 1; i weight.size(); i) { // 遍历科研物品for(int j 0; j bagweight; j) { // 遍历行李箱容量// 如果装不下这个物品,那么就继承dp[i - 1][j]的值if (j weight[i]) dp[i][j] dp[i - 1][j];// 如果能装下,就将值更新为 不装这个物品的最大值 和 装这个物品的最大值 中的 最大值// 装这个物品的最大值由容量为j - weight[i]的包任意放入序号为[0, i - 1]的最大值 该物品的价值构成else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);}}cout dp[weight.size() - 1][bagweight] endl;
}int main() {while(cin n bagweight) {solve();}return 0;
算法使用两层嵌套循环来补全dp数组外层执行weight.size()次即n次内层执行了bagweight1次定为m次时间复杂度为O(n*m)空间复杂度使用了二维数组O(n*m)。
一维
滚动数组不太理解周末看看。
代码随想录 (programmercarl.com)
// 一维dp数组实现
#include iostream
#include vector
using namespace std;int main() {// 读取 M 和 Nint M, N;cin M N;vectorint costs(M);vectorint values(M);for (int i 0; i M; i) {cin costs[i];}for (int j 0; j M; j) {cin values[j];}// 创建一个动态规划数组dp初始值为0vectorint dp(N 1, 0);// 外层循环遍历每个类型的研究材料for (int i 0; i M; i) {// 内层循环从 N 空间逐渐减少到当前研究材料所占空间for (int j N; j costs[i]; --j) {// 考虑当前研究材料选择和不选择的情况选择最大值dp[j] max(dp[j], dp[j - costs[i]] values[i]);}}// 输出dp[N]即在给定 N 行李空间可以携带的研究材料最大价值cout dp[N] endl;return 0;
} 分割等和子集
416. 分割等和子集 - 力扣LeetCode 本来想着直接排序然后依次加入最小的数然后发现果然有错[1,1,2,2]。 以[1,5,11,5]这个题例为例可以抽象为 一个背包容量为11剩余元素只能使用1次是否能装满这个容量为11的背包。0-1背包问题。 DP数组含义容量为j的最大价值为dp[j],当dp[target] target时表示能装满此处的target为数组sum的一半因为两个子集和要相等即能实现分割等和子集。 背包容量从0到10001因为数字总和不超过20000则target10000,dp数组长度到达10001就够了。 dp[j] max(dp[j],dp[j - nums[i]] nums[i]); 对dp的初始化由于nums数组全为正整数可以全部初始化为0若存在负数则应初始化为INT_MIN。
遍历顺序物品遍历在外背包遍历在内层且内层倒序遍历。参考代码随想录 (programmercarl.com)
最后需考虑当dp[target] target时返回true否则为false。
此外若sum%2 1则表明sum为奇数不存在两个相等的子数组和return false。剪枝。
class Solution {
public:bool canPartition(vectorint nums) {int sum 0; for(auto x:nums){sum x; // 计算数组元素的总和}// 如果总和是奇数那么不能平分直接返回falseif(sum%2 1)return false;// 计算目标和即每个子集应该达到的和const int target sum/2;// 初始化动态规划数组dp大小为10001初值都为0// dp[j]表示是否能够从前i个数字中选取一些数字使得这些数字的和为jvectorintdp(10001, 0);// 遍历数组中的每个数字for(int i 0; i nums.size();i){// 从大到小遍历目标和及其以下的值for(int j target; j nums[i]; j--){// 更新dp[j]选取或不选取当前数字取两种情况的最大值dp[j] max(dp[j],dp[j - nums[i]] nums[i]);}}// 如果dp[target]等于target说明可以找到和为target的子集返回trueif(dp[target] target)return true;return false;}
};算法的时间复杂度为O(n^2)空间复杂度为O(n)。
