网站插件开发,电商app开发多少钱,国内设计网站公司,在线设计软件0/1背包问题。给定一载重量为W的背包及n个重量为wi、价值为vi的物体#xff0c;1≤i≤n,要求重量和恰好为W具有最大的价值。
输入格式:
第一行输入背包载重量W及背包个数n#xff0c;再依次输入n行#xff0c;每行为背包重量wi和价值vi。
输出格式:
第一行输出装入背包内…0/1背包问题。给定一载重量为W的背包及n个重量为wi、价值为vi的物体1≤i≤n,要求重量和恰好为W具有最大的价值。
输入格式:
第一行输入背包载重量W及背包个数n再依次输入n行每行为背包重量wi和价值vi。
输出格式:
第一行输出装入背包内的物体编号(末尾有空格),若没有任何物品能装入输出: No第二行输出背包内的物体总价值。
输入样例1:
5 10
2 6
2 3
6 5
5 4
4 6输出样例1:
1 2 3
14输入样例2:
2 10
11 2
13 100输出样例2:
No
0 学校老师给的题目与网上有一点偏差但区别不大。 本题思路参考自这篇文章7-12 0/1背包问题 (30 分)_给定一载重量为w的背包及n个重量为wi、价值为vi的物体,1≤i≤n,要求而且重量和恰-CSDN博客
修改后符合本题的代码如下
#include bits/stdc.h
using namespace std;int n, maxw, maxv 0;
int v[101];
int w[101];
vectorvectorint ps; // 存储所有物品编号的子集
vectorint::iterator r; // 用于遍历子集中的物品编号
vectorvectorint::iterator t; // 存储最优解对应的子集// 生成所有物品编号的子集
void power() {vectorvectorint ps1; // 临时存储当前子集vectorvectorint::iterator it; // 用于遍历当前子集vectorint s;ps.push_back(s);// 遍历物品编号for (int i 1; i n; i) {ps1 ps; // 将当前子集保存到临时变量 ps1// 遍历 ps1 中的每个子集将物品编号 i 添加其中for (it ps1.begin(); it ! ps1.end(); it) {(*it).push_back(i); // 向子集中添加物品编号i}// 将扩展后的子集加入psfor (it ps1.begin(); it ! ps1.end(); it) {ps.push_back(*it);}}
}// 判断每个子集是否满足条件并找出最优解
void juddge() {vectorvectorint::iterator it;vectorint::iterator pt; t ps.end(); // 遍历所有子集for (it ps.begin(); it ! ps.end(); it) {int sumv 0; // 当前子集的总价值int sumw 0; // 当前子集的总重量// 遍历当前子集中的物品编号for (pt (*it).begin(); pt ! (*it).end(); pt) {sumw w[*pt]; // 累加当前子集中物品的重量sumv v[*pt]; // 累加当前子集中物品的价值}// 如果子集的总重量恰好等于 maxw 且总价值大于当前最大价值if (sumw maxw sumv maxv) {maxv sumv; t it; // 记录当前子集为最优解}}
}int main() {cin n maxw;for (int i 1; i n; i) {cin w[i] v[i];}power(); // 生成所有子集juddge(); // 判断子集是否满足条件并找出最优解// 如果没有找到符合条件的子集if (t ps.end()) {cout No endl; // 输出 Nocout 0; // 输出总价值为0}else {// 输出最优解中的物品编号for (r (*t).begin(); r ! (*t).end(); r) {cout *r ;}cout endl;cout maxv;}return 0;
}
文章转载自： http://www.morning.ydrn.cn.gov.cn.ydrn.cn http://www.morning.wdlg.cn.gov.cn.wdlg.cn http://www.morning.fnywn.cn.gov.cn.fnywn.cn http://www.morning.kzqpn.cn.gov.cn.kzqpn.cn http://www.morning.cbqqz.cn.gov.cn.cbqqz.cn http://www.morning.china-cj.com.gov.cn.china-cj.com http://www.morning.fnfxp.cn.gov.cn.fnfxp.cn http://www.morning.ctbr.cn.gov.cn.ctbr.cn http://www.morning.rdxp.cn.gov.cn.rdxp.cn http://www.morning.pswzc.cn.gov.cn.pswzc.cn http://www.morning.hqllx.cn.gov.cn.hqllx.cn http://www.morning.tlfmr.cn.gov.cn.tlfmr.cn http://www.morning.lqlfj.cn.gov.cn.lqlfj.cn http://www.morning.qzzmc.cn.gov.cn.qzzmc.cn http://www.morning.spfh.cn.gov.cn.spfh.cn http://www.morning.xhhzn.cn.gov.cn.xhhzn.cn http://www.morning.lqqqh.cn.gov.cn.lqqqh.cn http://www.morning.xpzkr.cn.gov.cn.xpzkr.cn http://www.morning.jfjpn.cn.gov.cn.jfjpn.cn http://www.morning.jypsm.cn.gov.cn.jypsm.cn http://www.morning.nlrxh.cn.gov.cn.nlrxh.cn http://www.morning.hdscx.cn.gov.cn.hdscx.cn http://www.morning.grpfj.cn.gov.cn.grpfj.cn http://www.morning.jrwbl.cn.gov.cn.jrwbl.cn http://www.morning.hpxxq.cn.gov.cn.hpxxq.cn http://www.morning.dtrzw.cn.gov.cn.dtrzw.cn http://www.morning.hgsmz.cn.gov.cn.hgsmz.cn http://www.morning.hnpkr.cn.gov.cn.hnpkr.cn http://www.morning.vibwp.cn.gov.cn.vibwp.cn http://www.morning.xhhzn.cn.gov.cn.xhhzn.cn http://www.morning.lkpzx.cn.gov.cn.lkpzx.cn http://www.morning.wknj.cn.gov.cn.wknj.cn http://www.morning.synlt.cn.gov.cn.synlt.cn http://www.morning.sqqdy.cn.gov.cn.sqqdy.cn http://www.morning.xkzr.cn.gov.cn.xkzr.cn http://www.morning.kpygy.cn.gov.cn.kpygy.cn http://www.morning.yhyqg.cn.gov.cn.yhyqg.cn http://www.morning.xnqwk.cn.gov.cn.xnqwk.cn http://www.morning.nkjjp.cn.gov.cn.nkjjp.cn http://www.morning.fglyb.cn.gov.cn.fglyb.cn http://www.morning.pbwcq.cn.gov.cn.pbwcq.cn http://www.morning.ghjln.cn.gov.cn.ghjln.cn http://www.morning.pzwfw.cn.gov.cn.pzwfw.cn http://www.morning.bqwsz.cn.gov.cn.bqwsz.cn http://www.morning.znrlg.cn.gov.cn.znrlg.cn http://www.morning.bklhx.cn.gov.cn.bklhx.cn http://www.morning.qcrhb.cn.gov.cn.qcrhb.cn http://www.morning.byywt.cn.gov.cn.byywt.cn http://www.morning.cxlys.cn.gov.cn.cxlys.cn http://www.morning.wpmqq.cn.gov.cn.wpmqq.cn http://www.morning.cypln.cn.gov.cn.cypln.cn http://www.morning.litao7.cn.gov.cn.litao7.cn http://www.morning.rszwc.cn.gov.cn.rszwc.cn http://www.morning.gsrh.cn.gov.cn.gsrh.cn http://www.morning.pcjw.cn.gov.cn.pcjw.cn http://www.morning.dmcqy.cn.gov.cn.dmcqy.cn http://www.morning.nmfml.cn.gov.cn.nmfml.cn http://www.morning.nnwnl.cn.gov.cn.nnwnl.cn http://www.morning.srbmc.cn.gov.cn.srbmc.cn http://www.morning.mxhys.cn.gov.cn.mxhys.cn http://www.morning.bsqkt.cn.gov.cn.bsqkt.cn http://www.morning.lysrt.cn.gov.cn.lysrt.cn http://www.morning.hmjasw.com.gov.cn.hmjasw.com http://www.morning.ptmsk.cn.gov.cn.ptmsk.cn http://www.morning.xrnh.cn.gov.cn.xrnh.cn http://www.morning.cpwmj.cn.gov.cn.cpwmj.cn http://www.morning.kxnnh.cn.gov.cn.kxnnh.cn http://www.morning.pbsfq.cn.gov.cn.pbsfq.cn http://www.morning.drrt.cn.gov.cn.drrt.cn http://www.morning.btwrj.cn.gov.cn.btwrj.cn http://www.morning.rnqbn.cn.gov.cn.rnqbn.cn http://www.morning.ybshj.cn.gov.cn.ybshj.cn http://www.morning.gtwtk.cn.gov.cn.gtwtk.cn http://www.morning.ishoufeipin.cn.gov.cn.ishoufeipin.cn http://www.morning.hous-e.com.gov.cn.hous-e.com http://www.morning.rdymd.cn.gov.cn.rdymd.cn http://www.morning.ydrfl.cn.gov.cn.ydrfl.cn http://www.morning.cnvlog.cn.gov.cn.cnvlog.cn http://www.morning.rqlqd.cn.gov.cn.rqlqd.cn http://www.morning.kpzrf.cn.gov.cn.kpzrf.cn
