室内设计师培训班费用_外贸必备的app_软文拟发布的平台与板块_如何做个网站推广自己产品

整体思路：
本题通过动态规划的方法解决背包问题，针对两个不同的问题要求分别进行了两次动态规划计算。
利用 dp 数组存储中间结果，通过状态转移方程逐步推导出在不同物品数量和背包容量情况下的最大价值。

第一问解题思路：
定义 dp[i][j] 表示在前 i 个物品中，背包容量不超过 j 时能装下的最大价值。
状态转移方程为：dp[i][j] = max(dp[i - 1][j], (j >= v[i])? dp[i - 1][j - v[i]] + w[i] : dp[i - 1][j])，即考虑不选第 i 个物品（直接继承前 i - 1 个物品在当前容量的最大价值）和选第 i 个物品（前提是背包容量够放，此时价值是前 i - 1 个物品在剩余容量的最大价值加上第 i 个物品的价值）这两种情况取最大值。
通过两层循环，外层遍历物品，内层遍历背包容量，逐步填充 dp 数组，最终得到第一问的答案 dp[n][V]。

第二问解题思路：
重新定义 dp[i][j] 表示在前 i 个物品中，背包容量恰好为 j 时能装下的最大价值。
初始化时，对于没有物品可选但背包有容量的情况标记为不可能装满（设为 -1）。
状态转移方程类似第一问，但多了一个限制条件，即只有在前 i - 1 个物品、背包容量为 j - v[i] 时的状态是可以恰好装满背包（不是 -1 标记的情况）时，才考虑选择第 i 个物品来更新 dp[i][j] 的值，同样通过两层循环填充 dp 数组，最后根据 dp[n][V] 的值判断是否能恰好装满背包并输出相应结果。

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<stdio.h>
#include<string.h>using namespace std;// 定义一个较大的常量，用于表示数组的最大长度，这里假设最多有1010个物品或背包容量最大为1010等情况
const int N = 1010;  
int v[N], w[N];  // 分别用于存储每个物品的体积和价值的数组，索引对应物品编号（从1开始）
int n, V;        // n表示物品的个数，V表示背包能容纳的最大体积// dp数组用于存储动态规划过程中的中间结果，dp[i][j]有两种含义：
// 1. 对于第一问：表示在前i个物品中，背包容量不超过j时能装下的最大价值。
// 2. 对于第二问：表示在前i个物品中，背包容量恰好为j时能装下的最大价值。
int dp[N][N];  int main() {// 输入物品个数和背包的最大体积cin >> n >> V;  // 循环读取每个物品的体积和价值，注意这里索引从1开始，符合常规的计数习惯（第1个物品、第2个物品等）for (int i = 1; i <= n; ++i)  scanf("%d %d", &v[i], &w[i]);// 以下是求解第一问的动态规划过程// 外层循环遍历每个物品，从第1个物品开始，逐步考虑到所有的n个物品for (int i = 1; i <= n; ++i++) {  // 内层循环遍历背包的不同容量情况，从容量为1开始，到最大容量Vfor (int j = 1; j <= V; ++j) {  // 初始化dp[i][j]，先默认不选第i个物品时的情况，此时最大价值等于前i - 1个物品在容量为j时的最大价值dp[i][j] = dp[i - 1][j];  // 判断背包当前容量j是否能够容纳第i个物品（即体积是否够放）if (j >= v[i])  // 如果能放，就需要比较放和不放第i个物品哪种情况能让背包中物品的价值更大// 不放就是dp[i - 1][j]，放的话就是在前i - 1个物品、背包容量为j - v[i]时的最大价值基础上，加上第i个物品的价值w[i]dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);  }}// 完成动态规划计算后，输出第一问的结果，即在前n个物品、背包容量为V时能装下的最大价值cout << dp[n][V] << endl;  // 以下是求解第二问的动态规划过程// 先将整个dp数组初始化为0，用于重新计算第二问的情况memset(dp, 0, sizeof dp);  // 对于容量大于0且没有物品可选（即前0个物品）的情况，将其价值设为 -1，表示这种情况不可能恰好装满背包，是一种特殊的标记for (int j = 1; j <= V; ++j) dp[0][j] = -1;  // 外层循环同样遍历每个物品，从第1个物品开始考虑for (int i = 1; i <= n; ++i) {  // 内层循环遍历不同的背包容量情况，从容量为1到最大容量Vfor (int j = 1; j <= V; ++j) {  // 先默认不选第i个物品时的情况，和第一问类似，此时最大价值等于前i - 1个物品在容量为j时的最大价值dp[i][j] = dp[i - 1][j];  // 判断背包当前容量j是否能容纳第i个物品，并且在前i - 1个物品、背包容量为j - v[i]时的状态是可以恰好装满背包的（不是 -1标记的那种不可能装满的情况）if (j >= v[i] && dp[i - 1][j - v[i]]!= -1)  // 如果满足条件，同样比较放和不放第i个物品哪种情况能让背包恰好装满时的价值更大dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);  }}// 判断最终在前n个物品、背包容量为V时，如果得到的结果是 -1，表示这种情况下无法恰好装满背包，按照要求输出0if (dp[n][V] == -1) cout << 0;  // 如果不是 -1，说明能恰好装满背包，输出此时的最大价值else cout << dp[n][V];  
}
// 64 位输出请用 printf("%lld")

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

• 计算数组总和并判断可行性：
  首先遍历输入的数组 nums，计算出所有元素的总和 sum。
  如果总和 sum 是奇数，那无论怎么划分都不可能得到两个和相等的子集，直接返回 false。
  若总和是偶数，则将其除以2，得到目标和，后续的操作就是围绕能否凑出这个目标和来进行判断。
• 初始化动态规划数组 dp：
  创建二维布尔类型的 dp 数组，dp[i][j] 的含义是在数组 nums 的前 i 个元素中（实际对应 nums[0] 到 nums[i - 1]），是否存在一些元素的和等于 j。
  对于没有元素可选（i = 0）但目标和 j 大于 0 的情况，显然是无法凑出目标和的，所以将 dp[0][j]（j > 0）设为 false，而 dp[0][0] 设为 true，表示和为 0 不需要任何元素就可以达到，这是边界情况的设定。
• 动态规划状态转移过程：
  通过两层嵌套循环来填充 dp 数组，外层循环变量 i 从 1 到 n（n 是数组 nums 的元素个数），表示逐步考虑数组中的每个元素。
  内层循环变量 j 从 1 到 sum（前面计算得到的目标和），表示不同的目标和情况。
  对于dp[i][j]，先默认不选第 i 个元素时的情况，其值等于前 i - 1 个元素能否凑出和为 j 的情况，即 dp[i][j] = dp[i - 1][j]。
  然后判断当前目标和 j 是否大于等于第 i 个元素的值（因为索引的对应关系，实际判断 j >= nums[i - 1]），并且在前 i - 1 个元素中已经能够凑出和为 j - nums[i - 1] 的情况（即 dp[i - 1][j - nums[i - 1]] 为 true），如果满足这两个条件，说明选了第 i 个元素后能凑出和为 j，则将 dp[i][j] 更新为 true。
• 得出最终结论：
  当完成整个动态规划的状态转移后，最终查看 dp[n][sum] 的值，若其为 true，就意味着可以从数组 nums 中选出一些元素凑出目标和，也就是可以将数组分割成两个子集，使得两个子集的元素和相等；若为 false，则表示无法做到这样的分割。

class Solution {const int N = 20010;
public:bool canPartition(vector<int>& nums) {// 获取输入数组nums的元素个数int n = nums.size();  int sum = 0;// 计算数组nums中所有元素的总和for (auto& x : nums) sum += x;  // 如果总和是奇数，那么肯定无法分割成两个和相等的子集，直接返回falseif (sum % 2!= 0) return false;  // 如果总和是偶数，将总和除以2，得到目标和，后续就是看能否从数组中选出一些元素凑出这个目标和else sum /= 2;  // dp数组用于动态规划过程中的状态记录，dp[i][j]表示在nums数组的前i个元素（即nums[0]到nums[i - 1]，注意索引偏移）中，是否存在一些元素的和等于j// 初始化dp数组大小为(n + 1) * (sum + 1)，并将所有元素初始值设为false，这里vector<bool>在初始化时会进行默认的初始化，不过为了清晰明确逻辑，我们显式地进行初始化vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));  // 当没有元素可选（即i = 0），但目标和j大于0时，肯定是无法凑出目标和的，所以将这部分设为false，不过dp[0][0]设为true，表示和为0时不需要任何元素就可以达到（边界情况）for (int j = 1; j <= sum; ++j) dp[0][j] = false;  // 以下开始动态规划的状态转移过程for (int i = 1; i <= n; ++i) {  for (int j = 1; j <= sum; ++j) {// 初始化dp[i][j]，先默认不选第i个元素时的情况，此时是否能凑出和为j就取决于前i - 1个元素的情况，所以直接继承dp[i - 1][j]的值dp[i][j] = dp[i - 1][j];  // 判断当前目标和j是否大于等于第i个元素的值nums[i - 1]（索引偏移，因为循环里i从1开始，对应nums里的索引是i - 1）// 并且在前i - 1个元素中已经能够凑出和为j - nums[i - 1]的情况（即dp[i - 1][j - nums[i - 1]]为true）if (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]])  // 如果满足上述条件，说明选了第i个元素后能凑出和为j，将dp[i][j]设为truedp[i][j] = true;  }}// 最终返回在前n个元素中能否凑出目标和sum的结果，即dp[n][sum]的值，如果为true表示可以将数组分割成两个子集使得元素和相等，否则不行return dp[n][sum];  }
};

整体思路：
本题的核心思路是利用动态规划来解决类似于背包问题的优化场景，通过合理地划分石头，使得两堆石头的重量差值尽可能小，进而得到最后剩下石头的最小重量。关键在于将问题转化为求在一定容量限制下能装入的最大重量问题。
具体步骤：

• 计算石头总重量并确定目标容量：
  首先通过循环遍历输入的石头重量数组 stones，累加计算出所有石头的总重量 sum。
  然后将总重量sum除以 2 得到 t，这里把问题抽象成一个类似背包容量的概念，目标是从这些石头中选取一些石头，使其重量之和尽量接近 t，这样就能让两堆石头的重量尽可能均衡，最终剩下的石头重量最小。
• 初始化动态规划数组 dp：
  创建一维整数数组 dp，长度为 t + 1，并将所有元素初始化为 0。dp[j]表示在容量为 j 的情况下（类比背包容量），所能装入的石头重量的最大值（即从石头中挑选部分石头组成的最大重量和）。
• 动态规划状态转移过程：
  外层循环使用变量 i 从 0 到 n - 1（n 为石头数组 stones 的元素个数），依次遍历每一块石头，考虑将每块石头放入 “背包” 的情况。
  内层循环使用变量 j 从目标容量 t 开始，倒序遍历到当前石头的重量 stones[i]。倒序遍历是非常关键的一点，它保证了在计算 dp[j] 时，每个石头只会被考虑放入 “背包” 一次，避免了重复选取同一块石头的错误情况。
  在每次内层循环中，对于 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])。
• 计算最后剩下石头的最小重量：
  经过上述动态规划过程，dp[t] 就表示在容量为 t 的情况下能装入的最大重量。由于我们希望两堆石头重量尽可能接近总重量的一半，所以最后剩下的石头重量可以通过总重量 sum 减去两倍的 dp[t]来得到。如果总重量能被 2 整除且正好能平均分成两堆，那么结果就是 0；否则就得到了最后剩下那块石头的最小可能重量。

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {// 获取石头数组的元素个数int n = stones.size();  int t = 0, sum = 0;// 计算所有石头的总重量for (auto& x : stones) sum += x;  // 将总重量除以2，得到一个目标值t，这里的思路是把问题转化为尽量装满一个容量为t的“背包”// 目的是让分成的两堆石头重量尽可能接近，这样最后剩下的石头重量就最小t = sum / 2;  // 创建动态规划数组dp，dp[j]表示在容量为j的情况下，能装入“背包”（这里可以理解为从石头中选取一些石头组成的重量和）的最大重量vector<int> dp(t + 1, 0);  // 开始动态规划的状态转移过程，外层循环遍历每一块石头for (int i = 0; i < n; ++i) {  // 内层循环从目标容量t开始，倒序遍历到当前石头的重量stones[i]，倒序遍历是为了保证每个石头只被使用一次（避免重复使用同一块石头）for (int j = t; j >= stones[i]; --j) {  // 对于dp[j]，需要比较两种情况取最大值来更新其值：// 1. 不选当前这块石头，即维持之前dp[j]的值不变。// 2. 选当前这块石头，此时需要在前容量为j - stones[i]的最大重量基础上，加上当前石头的重量stones[i]，即dp[j - stones[i]] + stones[i]。dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);  }}// 根据前面的思路，将所有石头分成两堆，使得两堆重量尽可能接近总重量的一半t，那么最后剩下的石头重量就是总重量sum减去两倍的能装入容量为t的“背包”的最大重量dp[t]return sum - 2 * dp[t];  }
};