yii2 网站开发,唐卡装饰公司电话,销售怎么做,the7 wordpress下载01 背包
题目描述
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物品价值总和最大。
题目分析
每一件物品其实只有两个状态#xff0c;取或者不取…01 背包
题目描述
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
题目分析
每一件物品其实只有两个状态取或者不取所以可以使用回溯法搜索出所有的情况那么时间复杂度就是$o(2^n)$这里的n表示物品数量。
所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化 确定递推公式
再回顾一下dp[i][j]的含义从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。
那么可以有两个方向推出来dp[i][j]
不放物品i由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以背包内的价值依然和前面相同。)放物品i由dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值
所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 数据结构
weight一个向量包含各个物品的重量。value一个向量包含各个物品的价值。bagweight一个整数代表背包的总容量。dp一个2D向量其中dp[i][j]表示用前i个物品填充容量为j的背包时可以达到的最大价值。
算法步骤
初始化首先使用物品0初始化dp数组的第一行。如果背包的容量大于等于物品0的重量则背包可以装下物品0所以对所有的j weight[0]dp[0][j]的值被设置为物品0的价值。填充DP表接下来遍历每个物品除了第一个已经处理过的物品并对每个可能的背包容量进行考虑。对于每个物品i和每个容量j 如果当前背包容量j小于物品i的重量则无法包含当前物品因此dp[i][j]的值就是不包含当前物品时的最大价值即dp[i-1][j]。如果当前背包容量可以容纳物品i则需要决定是包含还是不包含当前物品以达到最大价值。这通过比较不包含当前物品dp[i-1][j]和包含当前物品dp[i-1][j-weight[i]] value[i]时的价值来决定。选择这两种情况中的最大值作为dp[i][j]的值。
输出
通过查看dp数组的最后一个元素dp[weight.size() - 1][bagweight]可以得到使用给定物品填充指定容量背包的最大价值。
这种动态规划方法有效地解决了0/1背包问题通过构建一个解决方案的表格使得可以通过较小的子问题的解来构建出整个问题的解从而避免了冗余的计算和指数级的复杂度。
acm模式代码
#include iostream
#include vector
using namespace std;void test_2_wei_bag_problem1() {vectorint weight {1, 3, 4};vectorint value {15, 20, 30};int bagweight 4;// 二维数组vectorvectorint dp(weight.size(), vectorint(bagweight 1, 0));// 初始化for (int j 0 ; j weight[0]; j) { // 当然这一步如果把dp数组预先初始化为0了这一步就可以省略但很多同学应该没有想清楚这一点。dp[0][j] 0;}for (int j weight[0]; j bagweight; j) {dp[0][j] value[0];}// weight数组的大小 就是物品个数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];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() {test_2_wei_bag_problem1();
}
01背包一维 题目分析
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上表达式完全可以是dp[i][j] max(dp[i][j], dp[i][j - weight[i]] value[i]);
dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。
关于初始化一定要和dp数组的定义吻合否则到递推公式的时候就会越来越乱。
这样才能让dp数组在递归公式的过程中取的最大的价值而不是被初始值覆盖了。
所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的
acm模式代码
#include iostream
#include vectorvoid test_1_wei_bag_problem() {std::vectorint weight {1,3,4};std::vectorint value {15, 20 ,30};int bagweight 4;//初始化std::vectorint dp(bagweight 1, 0);for (int i 0; i weight.size(); i) {for (int j bagweight;j weight[i]; j--) {dp[j] std::max(dp[j], dp[j - weight[i]] value[i]);}}std::cout dp[bagweight] std::endl;
}int main() {test_1_wei_bag_problem();
} 416. 分割等和子集
题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 示例 1
输入nums [1,5,11,5]
输出true
解释数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2
输入nums [1,2,3,5]
输出false
解释数组不能分割成两个元素和相等的子集。提示
1 nums.length 2001 nums[i] 100
acm模式代码 #include iostream
#include vector
using namespace std;class Solution {
public:bool canPartition(vectorint nums) {int sum 0;for (int num : nums) {sum num;}if (sum % 2 ! 0) return false; // Early return if the sum is odd.int target sum / 2;vectorbool dp(target 1, false);dp[0] true; // Base case: zero sum is always possible.for (int num : nums) {for (int j target; j num; j--) {dp[j] dp[j] || dp[j - num];}}return dp[target];}
};int main() {Solution sol;vectorint nums {1, 5, 11, 5}; // Example inputbool canPart sol.canPartition(nums);if(canPart) {cout Can partition: YES endl;} else {cout Can partition: NO endl;}return 0;
}
