合肥做网站设计,部队网站模板jsp,wordpress level,站长之家综合查询工具01背包的滚动数组优化
【题目描述】
经典0—1背包问题,有n个物品#xff0c;编号为i的物品的重量为w[i]#xff0c;价值为c[i]#xff0c;现在要从这些物品中选一些物品装到一个容量为m的背包中#xff0c;使得背包内物体在总重量不超过m的前提下价值尽量大。
#include编号为i的物品的重量为w[i]价值为c[i]现在要从这些物品中选一些物品装到一个容量为m的背包中使得背包内物体在总重量不超过m的前提下价值尽量大。
#includeiostream
using namespace std;const int N 3500, M 12800;
int m, n, w[N], v[N], dp[M];
//状态 dp[j] 前i件物品在背包容量不超过j的情况下的最大价值
//状态转移方程 if (j w[i]) dp[j] max(dp[j], dp[j - w[i]] v[i]);
int main() {cin n m;for (int i 1; i n; i) cin w[i] v[i];//01背包的滚动数组优化for (int i 1; i n; i){for (int j m; j w[i]; j--) //01背包滚动数组优化的时候注意j要逆推{dp[j] max(dp[j],dp[j-w[i]]v[i]);}}cout dp[m] endl;return 0;
} 完全背包 特点n种物品每件物品有无限件但其实是有限 m/w[i]件 1268【例9.12】完全背包问题 【题目描述】 设有n种物品每种物品有一个重量及一个价值。但每种物品的数量是无限的同时有一个背包最大载重量为M今从n种物品中选取若干件(同一种物品可以多次选取)使其重量的和小于等于M而价值的和为最大。 #includeiostream
using namespace std;const int N 30, M 200;
int m, n, w[N], v[N], dp[M];
//状态 dp[j] 前i种物品在背包容量不超过j的情况下的最大价值
//状态转移方程
/*
dp[j]max{dp[j-0*w[i]]0*v[i],dp[j-1*w[i]]1*v[i],dp[j-2*w[i]]2*v[i],dp[j-3*w[i]]3*v[i],...dp[j-m/w[i]*w[i]]m/w[i]*v[i]}
*/
int main() {cin m n;for (int i 1; i n; i) cin w[i] v[i];//完全背包朴素版本for (int i 1; i n; i)for (int j m; j 1; j--)for (int k 1; k m / w[i]; k)if(jk*w[i]) dp[j] max(dp[j], dp[j - k * w[i]] k * v[i]);cout max dp[m] endl;return 0;
}多重背包 1269【例9.13】庆功会 【题目描述】 为了庆贺班级在校运动会上取得全校第一名成绩班主任决定开一场庆功会为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品可以补充他们的精力和体力。 多重背包 特点n种物品每件物品有指定数量s[i]真实数量上限min(m/w[i],s[i]) 状态 dp[j] 前i种物品在背包容量不超过j的情况下的最大价值 int main() { cin n m;for (int i 1; i n; i) cin w[i] v[i]s[i];//多重背包朴素版本for (int i 1; i n; i)for (int j m; j 1; j--)for (int k 1; k min(m / w[i], s[i]); k)//针对第i种物品得到选k件的最优解if (j k * w[i]) dp[j] max(dp[j], dp[j - k * w[i]] k * v[i]);cout dp[m] endl;return 0;
}
