怎么免费网做百度收录的网站无锡设计

当前位置： 首页 > news >正文

怎么免费网做百度收录的网站,无锡设计,物流网络货运平台,互联网公司 网站完全背包和01背包的区别就是#xff1a;可以多次选 一、完全背包#xff08;模版#xff09; 【模板】完全背包_牛客题霸_牛客网 #include iostream #includestring.h using namespace std; const int N1001; int n,V,w[N],v[N],dp[N][N]; //dp[i][j]表示… 完全背包和01背包的区别就是可以多次选 一、完全背包模版 【模板】完全背包_牛客题霸_牛客网 #include iostream #includestring.h using namespace std; const int N1001; int n,V,w[N],v[N],dp[N][N]; //dp[i][j]表示从前i个物品选体积不超过j的最大价值 //dp[i][j]max(dp[i-1][j],dp[i-1][j-v[i]]w[i],dp[i-1][j-2v[i]]2w[i]……) //数学dp[i][j-v[i]]max(dp[i-1][j-v[i]],dp[i-1][j-2v[i]]w[i]……) //dp[i][j]max(dp[i-1][j],dp[i][j-v[i]]) int main() {cinnV;for(int i1;in;i) cinv[i]w[i];//解决第一问for(int i1;in;i)for(int j1;jV;j){dp[i][j]dp[i-1][j];if(jv[i]) dp[i][j]max(dp[i][j],dp[i][j-v[i]]w[i]);} coutdp[n][V]endl;//解决第二问 //dp[i][j]表示从前i个物品选体积正好为j的最大价值memset(dp,0,sizeof dp);//约定-1表示状态选不到 当i0时 j1时 必然是没有状态的for(int j1;jV;j) dp[0][j]-1;for(int i1;in;i)for(int j1;jV;j){dp[i][j]dp[i-1][j];if(jv[i]dp[i][j-v[i]]!-1) dp[i][j]max(dp[i][j],dp[i][j-v[i]]w[i]);} cout(dp[n][V]-1?0:dp[n][V])endl;return 0; } 滚动数组的优化策略 区分01背包的优化得是从右往左而完全背包的优化得是从左往右 #include iostream #includestring.h using namespace std; const int N1001; int n,V,w[N],v[N],dp[N]; //dp[i][j]表示从前i个物品选体积不超过j的最大价值 //dp[i][j]max(dp[i-1][j],dp[i-1][j-v[i]]w[i],dp[i-1][j-2v[i]]2w[i]……) //数学dp[i][j-v[i]]max(dp[i-1][j-v[i]],dp[i-1][j-2v[i]]w[i]……) //dp[i][j]max(dp[i-1][j],dp[i][j-v[i]]) int main() //优化必须要从左往右 {cinnV;for(int i1;in;i) cinv[i]w[i];//解决第一问for(int i1;in;i)for(int jv[i];jV;j)dp[j]max(dp[j],dp[j-v[i]]w[i]);coutdp[V]endl;//解决第二问 //dp[i][j]表示从前i个物品选体积正好为j的最大价值memset(dp,0,sizeof dp);//约定-1表示状态选不到 当i0时 j1时 必然是没有状态的for(int j1;jV;j) dp[j]-0x3f3f3f3f;for(int i1;in;i)for(int jv[i];jV;j)dp[j]max(dp[j],dp[j-v[i]]w[i]);cout(dp[V]0?0:dp[V])endl;return 0; } 二、零钱兑换 . - 力扣LeetCode class Solution { public:int coinChange(vectorint coins, int amount) {//dp[i][j]表示从前i个里面选 正好凑成j所需要的最少硬币个数//如果不选i dp[i-1][j]//选1个i dp[i-1][j-coins[i-1]]1//dp[i][j]min(dp[i-1][j],dp[i-1][j-coins[i-1]]1,dp[i-1][j-2coins[i-1]]2……)//dp[i][j-coins[i-1]]min(dp[i-1][j-coins[i-1]],dp[i-1][j-2coins[i-1]]1……)//dp[i][j]min(dp[i-1][j],dp[i][j-coins[i-1]]1)const int INF0x3f3f3f3f;int ncoins.size();vectorvectorint dp(n1,vectorint(amount1));for(int j1;jamount;j) dp[0][j]INF;for(int i1;in;i)for(int j1;jamount;j){dp[i][j]dp[i-1][j];if(jcoins[i-1]) dp[i][j]min(dp[i][j],dp[i][j-coins[i-1]]1);}return dp[n][amount]INF?-1:dp[n][amount];} }; 滚动数组优化 class Solution { public:int coinChange(vectorint coins, int amount) {//dp[i][j]表示从前i个里面选 正好凑成j所需要的最少硬币个数//如果不选i dp[i-1][j]//选1个i dp[i-1][j-coins[i-1]]1//dp[i][j]min(dp[i-1][j],dp[i-1][j-coins[i-1]]1,dp[i-1][j-2coins[i-1]]2……)//dp[i][j-coins[i-1]]min(dp[i-1][j-coins[i-1]],dp[i-1][j-2coins[i-1]]1……)//dp[i][j]min(dp[i-1][j],dp[i][j-coins[i-1]]1)const int INF0x3f3f3f3f;int ncoins.size();vectorint dp(amount1,INF);dp[0]0;for(int i1;in;i)for(int jcoins[i-1];jamount;j)dp[j]min(dp[j],dp[j-coins[i-1]]1);return dp[amount]INF?-1:dp[amount];} }; 三、零钱兑换II . - 力扣LeetCode class Solution { public:int change(int amount, vectorint coins) {//dp[i][j]表示从前i个硬币选正好可以凑成总金额的硬币组合数//如果i不选 dp[i][j]dp[i-1][j]//如果i选1个 dp[i][j]dp[i-1][j-coins[i-1]]//dp[i][j]dp[i-1][j-coins[i-1]]dp[i-1][j-2coins[i-1]]……//dp[i][j]dp[i][j-coins[i-1]]int ncoins.size();//分析初始化 当j0 都是一种选法 当i0时 无论如何凑不出j 状态无效vectorvectorint dp(n1,vectorint(amount1));dp[0][0]1;for(int i1;in;i)for(int j0;jamount;j) //不会越界可以从0开始{dp[i][j]dp[i-1][j];if(jcoins[i-1]) dp[i][j]dp[i][j-coins[i-1]];}return dp[n][amount];} }; 滚动数组做优化 class Solution { public:int change(int amount, vectorint coins) {//dp[i][j]表示从前i个硬币选正好可以凑成总金额的硬币组合数//如果i不选 dp[i][j]dp[i-1][j]//如果i选1个 dp[i][j]dp[i-1][j-coins[i-1]]//dp[i][j]dp[i-1][j-coins[i-1]]dp[i-1][j-2coins[i-1]]……//dp[i][j]dp[i][j-coins[i-1]]int ncoins.size();//分析初始化 当j0 都是一种选法 当i0时 无论如何凑不出j 状态无效vectorint dp(amount1);dp[0]1;for(int i1;in;i)for(int jcoins[i-1];jamount;j) //不会越界可以从0开始dp[j]dp[j-coins[i-1]]; // 0不会影响填表return dp[amount];} }; 四、完全平方数 . - 力扣LeetCode class Solution { public: //不能用贪心策略 比如说1 4 9 组成12 444比9111好int numSquares(int n) {//1 4 9 16 25……//dp[i][j]表示从前i个数选刚好为j的最少数量const int INF0x3f3f3f3f;int msqrt(n);vectorint dp(n1,INF);//i0的时候 不可能凑成j j0时 i取1dp[0]0;for(int i1;im;i)for(int ji*i;jn;j)dp[j]min(dp[j],dp[j-i*i]1);return dp[n]; //一定能选得到因为1是平方数 所以必然能凑出来} }; 五、数位成本和为目标值的最大数字经典dp还原 . - 力扣LeetCode class Solution { public:string largestNumber(vectorint nums, int t) {//考虑数值长度问题每个数字有相应成本且长度均为1 //有若干物品求给定费用下所能选择的最大价值 完全背包//得到的就是最大位数 然后从后往前想办法还原回来vectorint dp(t1,-0x3f3f3f3f);//会有不存在的状态//dp[i][j]表示前i个数选择 正好为j的最大选择数目dp[0]1;for(int i1;i9;i)for(int jnums[i-1];jt;j)dp[j]max(dp[j],dp[j-nums[i-1]]1);//此时 dp[t]里存的就是选择的最大位数 然后要想办法进行还原if(dp[t]0) return 0;string ret;//开始还原 从后往前还原for(int i9;i1;–i){int unums[i-1];while(tudp[t]dp[t-u]1)//说明选到这个数了{retto_string(i);t-u;}}return ret;} }; 六、获得分数的方法数多重背包 . - 力扣LeetCode 该种类型题的具体分析请看第7题 class Solution { public:const int MOD1e97;int waysToReachTarget(int target, vectorvectorint types) {//dp[i][j]表示从前i个数选 恰好分数为j的方案数 选择方式是types[1] //如果不选这个数 dp[i-1][j]//如果选 1个 dp[i-1][j-p[0]] //如果选2个 dp[i-1][j-2p[0]]int ntypes.size();vectorvectorint dp(n1,vectorint(target1));//初始化当i为0时 dp[0][0]1;for(int i1;in;i){int counttypes[i-1][0],marktypes[i-1][1]; //count表示这道题的题数选择次数 mark表示这道题的分数for(int j0;jtarget;j){dp[i][j]dp[i-1][j];for(int k1;kcount;k){if(jk*mark) dp[i]j%MOD;}}}return dp[n][target];} }; 滚动数组优化  class Solution { public:const int MOD1e97;int waysToReachTarget(int target, vectorvectorint types) {//dp[i][j]表示从前i个数选 恰好分数为j的方案数 选择方式是types[1] //如果不选这个数 dp[i-1][j]//如果选 1个 dp[i-1][j-p[0]] //如果选2个 dp[i-1][j-2p[0]]vectorint dp(target1);//初始化当i为0时 dp[0]1;for(autop:types){int countp[0],markp[1]; //count表示这道题的题数选择次数 mark表示这道题的分数 //会用到上一层的状态所以滚动数组应该要从后往前for(int jtarget;j0;–j){countmin(count,j/mark);for(int k1;kcount;k)dpj%MOD;}}return dp[target];} }; 进阶优化 class Solution { public:const int MOD1e97;int waysToReachTarget(int target, vectorvectorint types) {//dp[i][j]表示从前i个数选 恰好分数为j的方案数 选择方式是types[1] //如果不选这个数 dp[i-1][j]//如果选 1个 dp[i-1][j-p[0]] //如果选2个 dp[i-1][j-2p[0]]//dp[i][j]dp[i-1][j-p[0]]……//dp[i][j-p[0]dp[i-1]][j-]vectorint dp(target1);//初始化当i为0时 dp[0]1;for(autop:types){int countp[0],markp[1]; //count表示这道题的题数选择次数 mark表示这道题的分数 //会用到上一层的状态所以滚动数组应该要从后往前for(int jmark;jtarget;j)dpj%MOD;for(int jtarget;j(count1)mark;–j)dp[j] (dp[j] - dp[j - mark(count 1)] MOD) % MOD; // 两个同余前缀和的差//防止搞出负数}return dp[target];} }; 七、带和限制的子多重集合的数目经典多重背包模版题 . - 力扣LeetCode 直接做滚动数组优化 class Solution { public:const int MOD1e97;int countSubMultisets(vectorint nums, int l, int r) {//01背包 每个数选或者不选 限制范围是l-r//dp[i][j]表示从前i个数选 凑成和恰好为j//但是需要一个哈希表来帮助我们知道每个数究竟可以选多少次unordered_mapint,int hash;int total0;for(autoe:nums) {totale;hash[e];}if(ltotal) return 0;rmin(r,total);vectorint dp(r1);//初始化 i0时 无数可选dp[0]hash[0]1;hash.erase(0);int t0;for(auto[x,c]:hash) //x是数 c是他的限制次数for(int jr;jx;–j){cmin(c,j/x);for(int k1;kc;k) //费时间 想办法用新的状态dpj%MOD; }int sum0;for(int jl;jr;j)sum(sumdp[j])%MOD;return sum;} }; 我们会发现由于数据量太大用循环会超时因此我们在这里不能用k那一层循环得换个方式 class Solution { public:const int MOD1e97;int countSubMultisets(vectorint nums, int l, int r) {//01背包 每个数选或者不选 限制范围是l-r//dp[i][j]表示从前i个数选 凑成和恰好为j//但是需要一个哈希表来帮助我们知道每个数究竟可以选多少次//类比完全背包的状态 dp[]unordered_mapint,int hash;int total0;for(autoe:nums) {totale;hash[e];}if(ltotal) return 0;rmin(r,total);vectorint dp(r1);dp[0]hash[0]1;hash.erase(0);// dp[i][j] dp[i-1][j-x]dp[i-1][j-2*x]……// dp[i][j-x]dp[i-1][j-2x]dp[i-1][j-3x]……int sum0;for(auto[x,c]:hash){sum min(sumx*c,r);//目前为止 能选的元素和之多为sum for (int j x; j sum; j)dpj % MOD; // 原地计算同余前缀和for (int j sum;j x * (c 1); j–)dpj % MOD; // 两个同余前缀和的差//防止搞出负数}int ret0;for(int jl;jr;j)ret(retdp[j])%MOD;return ret;} };