wordpress怎么搭建网站,电子商务网站的开发流程,营销方案100个软文,wordpress多语言版本完全背包
有 N N N件物品和一个容量是 M M M的背包。每种物品都有无限件可用。第 i i i件物品的体积是 v i v_i vi#xff0c;价值是 w i w_i wi。
求解将哪些物品装入背包#xff0c;可使这些物品的总体积不超过背包容量#xff0c;且总价值最大。
输出最大价值。…完全背包
有 N N N件物品和一个容量是 M M M的背包。每种物品都有无限件可用。第 i i i件物品的体积是 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用空格隔开分别表示第 i i i 件物品的体积和价值。
输出格式
输出一个整数表示最大价值。
样例 #1
样例输入 #1
4 5
1 2
2 4
3 4
4 5样例输出 #1
10提示 0 N , M ≤ 1000 0N,M≤1000 0N,M≤1000 0 v i , w i ≤ 1000 0v_i,w_i≤1000 0vi,wi≤1000
算法思想
状态表示
完全背包的特点是每种物品都有无限件可用。仍可以采用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
以上情况的前提是背包能够装得下 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 0\le k 0≤k并且 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件物品的数量 k k k时间复杂度为 O ( m / v ) O(m/v) O(m/v)
总的时间复杂的为 O ( n × m 2 / v ) O(n\times m^2/v) O(n×m2/v)。
代码实现
#include iostream
using namespace std;
const int N 1010, M 1010;
int f[N][N];
int main(){int n, m;cin n m;for(int i 1; i n; i){int v, w;cin v w;for(int j 0; j m; j){for(int k 0; 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 − k × v ] k × 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-k\times v]k\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−k×v]k×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 − k × v ] k × 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-k\times v]k\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−k×v]k×w}
也就是说 f [ i ] [ j ] max { f [ i − 1 ] [ j ] , f [ i ] [ j − v ] w } f[i][j] \max\{f[i-1][j], f[i][j−v]w\} f[i][j]max{f[i−1][j],f[i][j−v]w} f [ i ] [ j ] f[i][j] f[i][j]除了跟 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]有关只与 f [ i ] [ j − v ] w f[i][j−v]w f[i][j−v]w有关。
此时将状态表示的二维数组压缩为一维后 f [ j ] max { f [ j ] , f [ j − v ] w } f[j] \max\{f[j], f[j−v]w\} f[j]max{f[j],f[j−v]w}。需要注意的是这里 f [ j − v ] f[j−v] f[j−v]是 i i i阶段的状态由于 j − v ≤ v j-v\le v j−v≤v因此只需要从小到大枚举背包容量就可以保证使用 i i i阶段的状态 f [ j − v ] 来 f[j-v]来 f[j−v]来计算 f [ j ] f[j] f[j]的最大值。这样不但可以将状态的二维数组优化为一维也无需枚举第 i i i种物品的数量。
时间复杂度
状态数 n × m n\times m n×m状态计算时间复杂度为 O ( 1 ) O(1) O(1)
总的时间复杂的为 ( n × m ) (n\times m) (n×m)
代码实现
#include iostream
using namespace std;
const int M 1010;
int f[M];
int main()
{int n, m;cin n m;for(int i 1; i n; i ){int v, w;cin v w;for(int j v; j m; j ){f[j] max(f[j], f[j - v] w);}}cout f[m];return 0;
}相关练习
疯狂的采药
