自己做书画交易网站,汉中专业网站建设公司,宝塔wordpress更换域名,成都网上注册公司流程一、01背包问题
#xff08;一#xff09;题目
有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。
第i件物品的体积是 vi#xff0c;价值是 wi。
求解将哪些物品装入背包#xff0c;可使这些物品的总体积不超过背包容量#xff0c;且总价值最大。 输出最大价值…一、01背包问题
一题目
有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。
第i件物品的体积是 vi价值是 wi。
求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。
输入格式
第一行两个整数NV用空格隔开分别表示物品数量和背包容积。
接下来有 N行每行两个整数 vi,wi用空格隔开分别表示第i件物品的体积和价值。
输出格式
输出一个整数表示最大价值。
数据范围
0N,V≤1000 0vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5输出样例
8二 题解 【一】 二维动态规划
1状态f[i][j]定义前 i 个物品背包容量 j下的最优解最大价值 当前的状态依赖于之前的状态可以理解为从初始状态f[0][0] 0开始决策有 N
件物品则需要 N 次决 策每一次对第 i件物品的决策状态f[i][j]不断由之前的状态更新而来。
2当前背包容量不够j v[i]没得选因此前 i个物品最优解即为前 i−1个物品最优解 对应代码f[i][j] f[i - 1][j]。
3当前背包容量够可以选因此需要决策选与不选第i个物品 选f[i][j] f[i - 1][j - v[i]] w[i]。 不选f[i][j] f[i - 1][j] 。 我们的决策是如何取到最大价值因此以上两种情况取 max() 。
对应代码
#includeiostream
#includecstdio
#includecstringusing namespace std;const int N 1010;int v[N], w[N];
int f[N][N];int n, m;int main(){scanf(%d%d, n, m);for(int i 1; i n; i) scanf(%d%d, v[i], w[i]);for(int i 1; i n; i){for(int j 0; j m; j){f[i][j] f[i-1][j];if(j v[i]) f[i][j] max(f[i][j], f[i-1][j-v[i]]w[i]);}}printf(%d, f[n][m]);return 0;
}
【二】优化状态压缩二维变一维
将状态f[i][j]优化到一维f[j]实际上只需要做一个等价变形。
为什么可以这样变形呢我们定义的状态f[i][j]可以求得任意合法的i与j最优解但题目只需要求得最终状态f[n][m]因此我们只需要一维的空间来更新状态。
1状态f[j]定义N件物品背包容量j下的最优解。
2注意枚举背包容量j必须从m开始。
为什么一维情况下枚举背包容量需要逆序在二维情况下状态f[i][j]是由上一轮i - 1的状态得来的f[i][j]与f[i - 1][j]是独立的。而优化到一维后如果我们还是正序则有f[较小体积]更新到f[较大体积]则有可能本应该用第i-1轮的状态却用的是第i轮的状态。
例如一维状态第i轮对体积为 3的物品进行决策则f[7]由f[4]更新而来这里的f[4]正确应该f[i-1][4]但从小到大枚举j这里的f[4]在第i轮计算却变成了f[i][4]。当逆序枚举背包容量j时我们求f[7]同样由f[4]更新但由于是逆序这里的f[4]还没有在第i轮计算所以此时实际计算的f[4]仍然是f[i - 1][4]。
简单来说一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」逆序则不会有这样的问题。
状态转移方程为f[j] max(f[j], f[j - v[i]] w[i] 。
tips若通过减少维数来进行状态压缩要注意是否有一维循环需要逆序来保证更新所用到的状态没有被污染。
对应代码
#includeiostream
#includecstdio
#includecstringusing namespace std;const int N 1010;int v[N], w[N];
int f[N];int n, m;int main(){scanf(%d%d, n, m);for(int i 1; i n; i) scanf(%d%d, v[i], w[i]);for(int i 1; i n; i){for(int j m; j v[i]; -- j){f[j] max(f[j], f[j-v[i]]w[i]);}}printf(%d, f[m]);return 0;
}
二、完全背包
一题目
有 N 种物品和一个容量是V的背包每种物品都有无限件可用。
第i种物品的体积是 vi价值是 wi。
求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。
输入格式
第一行两个整数NV用空格隔开分别表示物品种数和背包容积。
接下来有N行每行两个整数 vi,wi用空格隔开分别表示第i种物品的体积和价值。
输出格式
输出一个整数表示最大价值。
数据范围
0N,V≤1000
0vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5输出样例
10二题解
闫式DP分析法 对应代码
二维DP
#includeiostream
#includecstdio
#includecstring
#includealgorithmusing namespace std;const int N 1010;int v[N], w[N];
int f[N][N];int n, m;int main(){scanf(%d%d, n, m);for(int i 1; i n; i) scanf(%d%d, v[i], w[i]);for(int i 1; i n; i){for(int j 0; j m; j){f[i][j] f[i-1][j];if(j v[i]) f[i][j] max(f[i][j], f[i][j-v[i]]w[i]); }}printf(%d, f[n][m]);return 0;
}
一维DP
#includeiostream
#includecstdio
#includecstring
#includealgorithmusing namespace std;const int N 1010;int v[N], w[N];
int f[N];int n, m;int main(){scanf(%d%d, n, m);for(int i 1; i n; i) scanf(%d%d, v[i], w[i]);for(int i 1; i n; i){for(int j 0; j m; j){f[j] f[j]; // 等价替换f[i][j] f[i-1][j];if(j v[i]) f[j] max(f[j], f[j-v[i]]w[i]); // 等价替换f[i][j] max(f[i][j], f[i][j-v[i]]w[i])// 总结替换的是f[i-1][...]还是f[i][...]取决于在该i层循环中等号右边的数组中出现的下标有没有更新过若更新过就是f[i][...] 反之则是f[i-1][...]}}printf(%d, f[m]);return 0;
}
简化
#includeiostream
#includecstdio
#includecstring
#includealgorithmusing namespace std;const int N 1010;int v[N], w[N];
int f[N];int n, m;int main(){scanf(%d%d, n, m);for(int i 1; i n; i) scanf(%d%d, v[i], w[i]);for(int i 1; i n; i){for(int j v[i]; j m; j){f[j] max(f[j], f[j-v[i]]w[i]); }}printf(%d, f[m]);return 0;
} 三、多重背包问题
一题目
有N 种物品和一个容量是V的背包。
第i种物品最多有 si 件每件体积是vi价值是wi。
求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入格式
第一行两个整数NV用空格隔开分别表示物品种数和背包容积。
接下来有N行每行三个整数 vi,wi,si用空格隔开分别表示第i种物品的体积、价值和数量。
输出格式
输出一个整数表示最大价值。
数据范围
0N≤1000 0V≤2000 0vi,wi,si≤2000
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2输出样例
10二题解
思路可以将多重背包问题转化为01背包问题。
1.朴素的转化思路
可以直接转化为有s[1]s[2]...s[n]个物品背包容量为V的01背包问题。
对应代码
#includeiostream
#includecstdio
#includecstring
#includealgorithmusing namespace std;const int N 110;int n, m;int f[N];int main(){scanf(%d%d, n, m);for(int i 1; i n; i){int v, w, s;scanf(%d%d%d, v, w, s);for(int j m; j 0; -- j){for(int k 1; k s; k){if(j k*v) f[j] max(f[j], f[j-k*v]k*w);}}}printf(%d, f[m]);return 0;
}
时间复杂度分析
ON*V*Si大约为10^9在本题目的数据范围限制下会超时。
2.优化
上述做法是将Si拆成了Si个1。
tips:
能否将Si拆成小于Si个数使这些数可以表示1~Si之间的所有数
答案是可以的。
结论其实只需要将Si拆成log(Si)上取整个数即可。这Si个数分别为2^0, 2^1, 2^2……2^log(Si)。
注意对于Si恰好等于以2为底的指数减1倍时是恰好符合题意的。而其他值在经过log(Si)上取整个数相加后仍会小于Si只需要将剩余的这部分单独拿出来即可。
对应代码
#includeiostream
#includecstdio
#includecstring
#includealgorithmusing namespace std;const int N 2010;int n, m;int f[N];struct good{int v, w;
};int main(){vectorgood goods;scanf(%d%d, n, m);for(int i 0; i n; i){int v, w, s;scanf(%d%d%d, v, w, s);for(int k 1; k s; k * 2){s - k;goods.push_back({k*v, k*w});}if(s 0) goods.push_back({s*v, s*w});}for(auto item: goods){for(int j m; j item.v; -- j){f[j] max(f[j], f[j-item.v]item.w);}}printf(%d, f[m]);return 0;
}
四、分组背包问题
一题目
有 N 组物品和一个容量是V的背包。
每组物品有若干个同一组内的物品最多只能选一个。 每件物品的体积是 vij价值是 wij其中 i 是组号j是组内编号。
求解将哪些物品装入背包可使物品总体积不超过背包容量且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 NV用空格隔开分别表示物品组数和背包容量。
接下来有N组数据
每组数据第一行有一个整数 S表示第i个物品组的物品数量每组数据接下来有 S行每行有两个整数 vij,wij用空格隔开分别表示第 i 个物品组的第j个物品的体积和价值
输出格式
输出一个整数表示最大价值。
数据范围
0N,V≤100
0Si≤100 0vij,wij≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5输出样例
8二题解
注意多重背包问题是分组背包问题的一个特殊情况。
分组背包问题同样也是01背包问题的一个变种。
对应代码
#includeiostream
#includecstdio
#includecstring
#includealgorithmusing namespace std;const int N 110;int n, m;int v[N], w[N];
int f[N];int main(){scanf(%d%d, n, m);for(int i 0; i n; i){int s;scanf(%d, s);for(int j 1; j s; j) scanf(%d%d, v[j], w[j]);for(int j m; j 0; -- j){for(int k 1; k s; k){if(j v[k]) f[j] max(f[j], f[j-v[k]]w[k]);}}}printf(%d, f[m]);return 0;
}
总结
01背包问题多重背包问题分组背包问题是同一大类背包问题。在i层循环中只能做一个选择即选与不选对于多重背包和分组背包的选对应的是多种选择。
而完全背包是另一大类问题。
