发布时间：2025-06-24 18:06:55  作者：北方职教升学中心  阅读量：379

状态转移方程类似第一问，但多了一个限制条件，即只有在前 i - 1 个物品、

🏳️‍🌈四、比如在一些动态规划问题中，如果状态转移只依赖于相邻的几个状态，就可以通过巧妙地复用数组空间来进一步减少空间的占用，不过这需要根据具体问题的特点来合理设计和实现。背包容量为j - v[i]时的最大价值基础上，加上第i个物品的价值w[i]dp[i][j]=max(dp[i][j],dp[i -1][j -v[i]]+w[i]);}}// 完成动态规划计算后，输出第一问的结果，即在前n个物品、

2. 最终版代码（空间优化）
   我们可以发现，在计算 dp[i][j]时，只用到了 dp[i - 1][...]的值，所以可以将二维数组压缩成一维数组来优化空间复杂度。

   第二问解题思路：
   重新定义 dp[i][j]表示在前 i 个物品中，背包容量恰好为 j 时能装下的最大价值。dp[j]表示在容量为 j的情况下（类比背包容量），所能装入的石头重量的最大值（即从石头中挑选部分石头组成的最大重量和）。背包容量为V时，如果得到的结果是 -1，表示这种情况下无法恰好装满背包，按照要求输出0if(dp[n][V]==-1)cout <<0;// 如果不是 -1，说明能恰好装满背包，输出此时的最大价值elsecout <<dp[n][V];}// 64 位输出请用 printf("%lld")

   🧡416. 分割等和子集

   
   整体思路：
   本题将能否分割数组成两个和相等子集的问题转化为一个 0/1 背包问题的变形来解决，通过动态规划的方式记录状态并进行状态转移，判断是否能从给定数组中选出一些元素，使其和等于数组总和的一半。01 背包问题概述

3. 🏳️‍🌈二、
   然后，定义动态规划的状态表示，一般会使用dp[i][j]，它的含义是将前 i 件物品放入容量为 j 的背包里所能获得的最大价值。问题分析与解法
4. • ❤️（一）表示状态
   • 🧡（二）状态转移方程
   • 🧡（三）代码实现
5. 🏳️‍🌈三、

   🧡（二）状态转移方程

   对于dp[i][j]这个状态，需要考虑第 i 件物品的选择情况，主要分为两种：
   不选第i件物品：此时背包里的最大价值就等于前 i - 1 件物品放入容量为 j 的背包里的最大价值，即 dp[i][j] = dp[i - 1][j]。如果总重量能被 2 整除且正好能平均分成两堆，那么结果就是 0；否则就得到了最后剩下那块石头的最小可能重量。关键在于将问题转化为求在一定容量限制下能装入的最大重量问题。

   🏳️‍🌈三、

   具体情况可以分为两种，即不选择 i位置的物品，结果为 f[i - 1][j]，
   以及选择 i位置的物品，结果为 f[i][j - v[i]] + w[i]，当然这是有前提条件的，即当前背包容量的最大值比这个物品的体积大，不然会越界

   

   🏳️‍🌈二、

   💚（四）空间优化

   除了前面提到的将二维数组压缩成一维数组这种常见的空间优化方式外，还可以进一步采用滚动数组等技巧来优化空间。
   步骤详解：

   • 计算数组总和并判断可行性：
     首先遍历输入的数组 nums，计算出所有元素的总和sum。以下是示例代码：

     #include<iostream>#include<vector>#include<unordered_map>usingnamespacestd;unordered_map<int,unordered_map<int,int>>memo;// 记忆化搜索计算最大价值intmemoizedSearch(vector<int>&weight,vector<int>&value,intindex,intcapacity){if(index ==0||capacity ==0){return0;}if(memo.count(index)&&memo[index].count(capacity)){returnmemo[index][capacity];}intres =memoizedSearch(weight,value,index -1,capacity);if(weight[index -1]<=capacity){res =max(res,memoizedSearch(weight,value,index -1,capacity -weight[index -1])+value[index -1]);}memo[index][capacity]=res;returnres;}intmain(){vector<int>weight ={2,3,4};vector<int>value ={3,4,5};intcapacity =5;cout <<"通过记忆化搜索背包能装的最大价值为: "<<memoizedSearch(weight,value,weight.size(),capacity)<<endl;return0;}

     通过使用 unordered_map 来作为记忆化的数据结构，记录不同 index（物品索引）和 capacity（背包容量）组合下的最大价值，大大减少了重复计算，提高了效率，但相较于动态规划，代码结构上还是相对复杂些，并且空间复杂度也会因为记忆化数据结构的使用有所增加。

   • 动态规划状态转移过程：
     外层循环使用变量i 从 0 到 n - 1（n 为石头数组 stones 的元素个数），依次遍历每一块石头，考虑将每块石头放入 “背包” 的情况。
   • 在每次循环中，先默认不选当前物品，然后判断如果背包容量够放当前物品，就比较放和不放当前物品哪种情况能得到更大价值，更新dp[i][j]的值。

     🧡（二）记忆化搜索

     为了避免暴力搜索中大量的重复计算问题，可以采用记忆化搜索的方式。
     初始化时，对于没有物品可选但背包有容量的情况标记为不可能装满（设为 -1）。

     📢博客主页：https://blog.csdn.net/2301_779549673
     📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
     📢本文由 JohnKi原创，首发于 CSDN🙉
     📢未来很长，值得我们全力奔赴更美好的生活✨

     

     

     文章目录

     • 🏳️‍🌈一、
       在每次内层循环中，对于dp[j]的更新，需要比较两种情况：一是不选当前这块石头，那么 dp[j]的值保持之前的状态不变；二是选当前这块石头，此时它的值应该是在前容量为j - stones[i]时的最大重量 dp[j - stones[i]] 的基础上，再加上当前石头的重量 stones[i]，取这两种情况的最大值来更新 dp[j]的值，即 dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])。
       若总和是偶数，则将其除以2，得到目标和，后续的操作就是围绕能否凑出这个目标和来进行判断。以下是简单的代码示例思路（实际完整代码可自行完善细节）：

       #include<iostream>#include<vector>usingnamespacestd;// 递归计算选择当前物品后的最大价值intbruteForce(vector<int>&weight,vector<int>&value,intindex,intcapacity){if(index ==0||capacity ==0){return0;}intres =bruteForce(weight,value,index -1,capacity);if(weight[index -1]<=capacity){res =max(res,bruteForce(weight,value,index -1,capacity -weight[index -1])+value[index -1]);}returnres;}intmain(){vector<int>weight ={2,3,4};vector<int>value ={3,4,5};intcapacity =5;cout <<"通过暴力搜索背包能装的最大价值为: "<<bruteForce(weight,value,weight.size(),capacity)<<endl;return0;}

       这种方法虽然简单直接，但是效率非常低，因为它会有大量的重复计算，随着物品数量和背包容量的增加，时间复杂度会呈指数级增长。
       如果总和sum是奇数，那无论怎么划分都不可能得到两个和相等的子集，直接返回 false。01 背包问题概述

01 背包问题是一个非常经典的动态规划问题，其场景设定为：给定一个背包，它有一定的容量限制，同时有若干种物品，每种物品都有对应的重量和价值，且每种物品只能选择放入背包一次（即选择 0 个或者 1 个），目标是在满足背包容量限制的条件下，求出能够装入背包的物品的最大价值总和。背包容量为V时能装下的最大价值cout <<dp[n][V]<<endl;// 以下是求解第二问的动态规划过程// 先将整个dp数组初始化为0，用于重新计算第二问的情况memset(dp,0,sizeofdp);// 对于容量大于0且没有物品可选（即前0个物品）的情况，将其价值设为 -1，表示这种情况不可能恰好装满背包，是一种特殊的标记for(intj =1;j <=V;++j)dp[0][j]=-1;// 外层循环同样遍历每个物品，从第1个物品开始考虑for(inti =1;i <=n;++i){// 内层循环遍历不同的背包容量情况，从容量为1到最大容量Vfor(intj =1;j <=V;++j){// 先默认不选第i个物品时的情况，和第一问类似，此时最大价值等于前i - 1个物品在容量为j时的最大价值dp[i][j]=dp[i -1][j];// 判断背包当前容量j是否能容纳第i个物品，并且在前i - 1个物品、

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>#include<vector>#include<stdio.h>#include<string.h>usingnamespacestd;// 定义一个较大的常量，用于表示数组的最大长度，这里假设最多有1010个物品或背包容量最大为1010等情况constintN =1010;intv[N],w[N];// 分别用于存储每个物品的体积和价值的数组，索引对应物品编号（从1开始）intn,V;// n表示物品的个数，V表示背包能容纳的最大体积// dp数组用于存储动态规划过程中的中间结果，dp[i][j]有两种含义：// 1. 对于第一问：表示在前i个物品中，背包容量不超过j时能装下的最大价值。01背包例题
❤️DP42 【模板】完全背包

整体思路：
本题通过动态规划的方法解决背包问题，针对两个不同的问题要求分别进行了两次动态规划计算。01背包例题