西宁网络公司做网站哪家好,网站制作设及的技术,上海闵行有阳性了,大连网站建设动态01背包理论基础
问题定义#xff1a;有n件物品和一个能装重量为w的背包#xff0c;第i件物品的重量是weight[i]#xff0c;得到的价值是value[i]。每件物品只能用一次#xff0c;求解将哪些物品装入背包获得的总价值最大。dp数组含义#xff1a;dp[i][j] 表示从下标为 [0…01背包理论基础
问题定义有n件物品和一个能装重量为w的背包第i件物品的重量是weight[i]得到的价值是value[i]。每件物品只能用一次求解将哪些物品装入背包获得的总价值最大。dp数组含义dp[i][j] 表示从下标为 [0,i] 的物品中选放进容量为j的背包中能得到的最大价值总和。确定递推公式在推导 dp[i][j] 时有两个方面一是不放物品i因为不放i物品所以dp[i][j] dp[i - 1][j]是只放前 i-1 个物品时的最大值二是放物品idp[i][j] dp[i - 1][j - weight[i]] value[i]。当背包容量小于i号物品重量时赋值第一方面的值否则赋值为两种情况的最大值。确定初始化dp[i][0] 由于背包容量为0根本放不进物品所以初始化为0。dp[0][j] 只放0号物品当 j weight[0] 时有值value[0]其他情况为0。遍历顺序这是重点要决定当前的状态必须由其左上角的状态决定。先遍历物品还是先背包容量都是可以的。
#include bits/stdc.h
using namespace std;
int n, bagweight;
void solve() {vectorint weight(n, 0);vectorint value(n, 0);for(int i 0; i n; i) {cin weight[i];}for(int i 0; i n; i) {cin value[i];}vectorvectorint dp(n, vectorint(bagweight 1, 0));for(int i weight[0]; i bagweight; i) { // 初始化dp[0][i] value[0];}for(int i 1; i n; i) {for(int j 1; 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[n - 1][bagweight] endl;
}
int main() {while(cin n bagweight) {solve();}return 0;
}滚动数组空间优化
我们观察二维数组的递推式可以发现 dp[i][j] 只与 i - 1 那一层的状态有关。因此可以用一个一维数组来表示状态。
dp[j] 表示容量为 j 的背包能获得的最大价值总和。因为在当前遍历过程中 dp 中存储的就是上一层的状态因此状态递推式为 dp[j] max(dp[j], dp[j - weight[i]] value[i])初始化下标0位置一定初始化为0其他位置为了递推式中的取最大值服务也初始化为0即可。遍历顺序背包容量的遍历需要从大到小倒序遍历是为了保证物品i只被放入一次。当前遍历中未处理的部分都是i-1那一层的值因此只有倒序遍历才能保证用到的状态没用过物品i。另一方面我们更新状态需要知道当前位置左侧的i-1状态 (j-weight[i])正序遍历就让左侧的状态变成当前层的。
#include bits/stdc.h
using namespace std;
int main() {int n, bagweight;while(cin n bagweight) {vectorint weight(n, 0);vectorint value(n, 0);for(int i 0; i n; i) {cin weight[i];}for(int i 0; i n; i) {cin value[i];}vectorint dp(bagweight 1, 0);for(int i 0; i n; i) {for(int j bagweight; j weight[i]; j--) {dp[j] max(dp[j], dp[j - weight[i]] value[i]);}}cout dp[bagweight] endl;}return 0;
}分割等和子集 其实用回溯可解但是会超时。因为每一个元素只能用一次考虑01背包试一下。 背包的大小为 sum / 2每一个元素看做物品其重量为元素值价值也为元素值。问题就转换成在sum / 2的背包中放入元素让背包尽可能的满由于重量等于价值就变成让价值总和尽量大最终查看最大值是否与sum / 2相等就能判断能不能分割。
class Solution{
public:bool canPartition(vectorint nums) {int sum 0;for(int num : nums) {sum num;}if(sum % 2) return false; // 和为奇数不可能分成相等的两份int target sum / 2; // 背包大小vectorint dp(target 1, 0);for(int i 0; i nums.size(); i) {for(int j target; j nums[i]; j--) {dp[j] max(dp[j], dp[j - nums[i]] nums[i]);}}return dp[target] target;}
};
