连云港网站建设电话,新增网站推广教程,政务网站源码,清华大学学生工作做网站有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件#xff0c;每件体积是 vi#xff0c;价值是 wi。
求解将哪些物品装入背包#xff0c;可使物品体积总和不超过背包容量#xff0c;且价值总和最大。 输出最大价值。
输入格式
第一行两个整数 N#xff0c;…有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件每件体积是 vi价值是 wi。
求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入格式
第一行两个整数 NV用空格隔开分别表示物品种数和背包容积。
接下来有 N 行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数表示最大价值。
数据范围
0N,V≤100
0vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2输出样例
10 朴素算法
#includeiostream
#includealgorithm
using namespace std;const int N 110;
int v[N],w[N],s[N],f[N][N];
int n,m;int main()
{cinnm;for(int i1;in;i) cinv[i]w[i]s[i];for(int i1;in;i){for(int j0;jm;j){for(int k0;ks[i]k*v[i]j;k){f[i][j] max(f[i][j],f[i-1][j-k*v[i]]k*w[i]);}}}coutf[n][m]endl;
}
多重背包的二进制优化方法
//本题考查多重背包的二进制优化方法
//将多重背包分成若干个01背包进行解题/*二进制优化下方举例说明
①假定物品件数s200
②二进制形式k[n]{1,2,4,8,16,32,64,73} 其所有值相加是200 可以凑出[0~200]的所有数
③除开最后一个数不是二进制形式73200-(1248163164)
④其余数若定64其中64[0~63]-[0~127]
⑤最后一个数73其中73[0~127]-[0~200] */#includeiostream
#includealgorithm
using namespace std;const int N 12010,M 2010;
int v[N],w[N],f[N];
int n,m;int main()
{cinnm;int cnt 0;for(int i1;in;i){int a,b,s;cinabs;// 输入第i种物品的体积a、价值b和数量sint k 1;while(ks){cnt;// 更新物品编号v[cnt] k*a;// 将当前数量的物品拆分成指数级别的多个子问题更新体积w[cnt] k*b;// 同样更新价值s-k;// 减去已经处理过的数量k*2; // 指数倍增加数量}if(s0)// 处理剩余的数量{cnt;v[cnt] s*a;w[cnt] s*b;}}n cnt;/*for(int i1;in;i){coutv[i]: v[i]endl;coutw[i]: w[i]endl;coutendl;}*///变成若干个01背包问题for(int i1;in;i){for(int jm;jv[i];j--){f[j] max(f[j],f[j-v[i]]w[i]);}}coutf[m]endl;}
