asp网站开发流程,网站建设与管理读书心得,广告设计培训专业,网站多个用户怎样建设多重背包
有 N N N件物品和一个容量是 M M M的背包。第 i i i种物品最多有 s i s_i si件#xff0c;每件的体积是 v i v_i vi#xff0c;价值是 w i w_i wi。
求解将哪些物品装入背包#xff0c;可使这些物品的总体积不超过背包容量#xff0c;且总价值最大。
输…多重背包
有 N N N件物品和一个容量是 M M M的背包。第 i i i种物品最多有 s i s_i si件每件的体积是 v i v_i vi价值是 w i w_i wi。
求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。
输出最大价值。
输入格式
第一行两个整数 N N N M M M用空格隔开分别表示物品数量和背包容积。
接下来有 N N N 行每行三个整数 v i v_i vi, w i w_i wi, s i s_i si用空格隔开分别表示第 i i i 件物品的体积价值和数量。
输出格式
输出一个整数表示最大价值。
样例 #1
样例输入 #1
4 5
1 2 3
2 4 1
3 4 3
4 5 2样例输出 #1
10提示 0 N ≤ 1000 , 0 M ≤ 2000 0N≤1000,0M\le2000 0N≤1000,0M≤2000 0 v i , w i , s i ≤ 2000 0v_i,w_i,s_i≤2000 0vi,wi,si≤2000
算法思想
状态表示
多重背包的特点是第 i i i种物品最多有 s i s_i si件。仍可以采用01背包的思想将处理每种物品作为一个阶段考虑在不同背包容量情况下的最大价值将其状态定义为 f [ i ] [ j ] f[i][j] f[i][j]表示对于前 i i i种物品在背包容量为 j j j的情况下背包获得的最大价值。
状态计算
在当前阶段对于第 i i i种物品来说有多种情况可以选择
放入 0 0 0件此时的最大价值为前 i − 1 i-1 i−1种物品在背包容量为 j j j的情况下的最大价值 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]。放入 1 1 1件此时背包的最大价值为前 i − 1 i-1 i−1种物品在背包容量为 j − v i j-v_i j−vi的情况下的最大价值 f [ i − 1 ] [ j − v i ] w i f[i-1][j-v_i]w_i f[i−1][j−vi]wi放入 2 2 2件此时背包的最大价值为前 i − 1 i-1 i−1种物品在背包容量为 j − 2 × v i j-2\times v_i j−2×vi的情况下的最大价值 f [ i − 1 ] [ j − 2 × v i ] 2 × w i f[i-1][j-2\times v_i]2\times w_i f[i−1][j−2×vi]2×wi…放入 k k k件此时背包的最大价值为前 i − 1 i-1 i−1种物品在背包容量为 j − k × v i j-k\times v_i j−k×vi的情况下的最大价值 f [ i − 1 ] [ j − k × v i ] k × w i f[i-1][j-k\times v_i]k\times w_i f[i−1][j−k×vi]k×wi…放入 s i s_i si件此时背包的最大价值为前 i − 1 i-1 i−1种物品在背包容量为 j − s i × v i j-s_i\times v_i j−si×vi的情况下的最大价值 f [ i − 1 ] [ j − s i × v i ] k × w i f[i-1][j-s_i\times v_i]k\times w_i f[i−1][j−si×vi]k×wi
以上情况的前提是背包能够装得下 k k k件第 i i i种物品也就是背包容量 j ≥ k × v i j\ge k\times v_i j≥k×vi。那么 f [ i ] [ j ] f[i][j] f[i][j]应该选择所有情况的最大值即 f [ i ] [ j ] max { f [ i − 1 ] [ j − k × v i ] k × w i } f[i][j] \max\{f[i-1][j-k\times v_i]k\times w_i\} f[i][j]max{f[i−1][j−k×vi]k×wi}其中 0 ≤ k ≤ s i 0\le k\le s_i 0≤k≤si并且 k × v i ≤ j k\times v_i \le j k×vi≤j。
初始状态 f [ 0 ] [ 0 ] f[0][0] f[0][0]表示将前 0 0 0种物品装入容量为 0 0 0的背包中的产生的最大价值为 0 0 0。
时间复杂度
状态数 n × m n\times m n×m状态计算时需要枚举第 i i i件物品的数量 s i s_i si时间复杂度为 O ( s i ) O(s_i) O(si)
总的时间复杂的为 O ( n × m × s ) O(n\times m\times s) O(n×m×s)。
代码实现
#include iostream
using namespace std;
const int N 1010, M 2010;
int f[N][N];
int main(){int n, m;cin n m;for(int i 1; i n; i){int v, w, s;cin v w s;for(int j 0; j m; j){for(int k 0; k s k * v j; k){f[i][j] max(f[i][j], f[i - 1][j - k * v] k * w);}}}coutf[n][m]endl;return 0;
}算法优化
根据上述状态转移方程考虑能否像完全背包一样的思路进行优化呢
由 f [ i ] [ j ] max { f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v ] w , f [ i − 1 ] [ j − 2 × v ] 2 × w . . . f [ i − 1 ] [ j − s × v ] s × w } f[i][j] \max\{f[i-1][j], f[i-1][j-v]w, f[i-1][j-2\times v]2\times w...f[i-1][j-s\times v]s\times w\} f[i][j]max{f[i−1][j],f[i−1][j−v]w,f[i−1][j−2×v]2×w...f[i−1][j−s×v]s×w}
可得 f [ i ] [ j − v ] max { f [ i − 1 ] [ j − v ] , f [ i − 1 ] [ j − 2 × v ] w , f [ i − 1 ] [ j − 3 × v ] 2 × w . . . f [ i − 1 ] [ j − ( s 1 ) × v ] ( s 1 ) × w } f[i][j - v] \max\{f[i-1][j - v], f[i-1][j-2\times v]w, f[i-1][j-3\times v]2\times w...f[i-1][j-(s1)\times v](s1)\times w\} f[i][j−v]max{f[i−1][j−v],f[i−1][j−2×v]w,f[i−1][j−3×v]2×w...f[i−1][j−(s1)×v](s1)×w} f [ i ] [ j − v ] f[i][j - v] f[i][j−v]和 f [ i ] [ j ] f[i][j] f[i][j]和对比可以发现多了一项 f [ i − 1 ] [ j − ( s 1 ) × v ] ( s 1 ) × w f[i-1][j-(s1)\times v](s1)\times w f[i−1][j−(s1)×v](s1)×w。如果计算出 f [ i ] [ j − v ] f[i][j - v] f[i][j−v]那么是否能得到 f [ i ] [ j ] f[i][j] f[i][j]呢举个栗子 也就是说知道前 s 1 s1 s1项的最大值并不能计算出前 s s s项的最大值因此不能采用完全背包的思想来优化多重背包。
二进制枚举
在计算状态的过程中需要枚举第 i i i种物品的数量 [ 0 , s i ] [0,s_i] [0,si]这里采用一种更高效的枚举方式——二进制枚举。例如当 s i 1023 s_i1023 si1023时可以将第 i i i种物品“打包”为 0 0 0件一组 1 1 1件一组 2 2 2件一组 4 4 4件一组… 512 512 512件一组
通过上述组与组之间的组合可以表示出 [ 0 , 1023 ] [0,1023] [0,1023]之间的任意一个数。如果把每组物品看成是01背包中的一种物品仅能选择一次那么就相当于用 10 10 10个新物品来表示原来的第 i i i个物品通过组合这 10 10 10个新物品就可以枚举出第 i i i个物品的全部方案。
时间复杂度
状态数 n × m n\times m n×m通过上述思想原来要枚举 s s s次现在只需要枚举 l o g s logs logs次
总的时间复杂的为 ( n × m × l o g s ) (n\times m\times logs) (n×m×logs)
代码实现
#include iostream
using namespace std;
const int N 1010 * 12, M 2010;
int v[N], w[N];
int f[M];
int main()
{int n, m, k 0;cin n m;for(int i 1; i n; i ){int a, b, s;cin a b s;//二进制拆分for(int j 1; j s; j * 2){v[ k] j * a;w[k] j * b;s - j;}//拆分后还有剩余if(s) v[ k] s * a, w[k] s * b;}n k; //拆分后实际的物品数量//01背包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]);cout f[m];return 0;
}
