赞
踩
目录
- template<typename T1,typename T2,typename T3>
- void Loading(T1 c, vector<T2>& w, vector<T3>& t, vector<bool>& v)
- {
- //冒泡排序
- for (int i = w.size() - 1; i > 0; i--)//扫描次数
- {
- for (int j = 0; j < i; j++)
- {
- if (w[j] > w[j + 1])
- {
- swap(w[j], w[j + 1]);//交换物品重量
- swap(t[j], t[j + 1]);//交换物品的序号
- }
- }
- }
-
- for (int k = 0; w[k] <= c; k++)
- {
- v[k] = true;
- c = c - w[k];//船的剩余装载量
- }
- }
- #include<iostream>
- #include<vector>
- #include<stdbool.h>
- using namespace std;
- template<typename T1,typename T2,typename T3>
- void Loading(T1 c, vector<T2>& w, vector<T3>& t, vector<bool>& v)
- {
- //冒泡排序
- for (int i = w.size() - 1; i > 0; i--)//扫描次数
- {
- for (int j = 0; j < i; j++)
- {
- if (w[j] > w[j + 1])
- {
- swap(w[j], w[j + 1]);//交换物品重量
- swap(t[j], t[j + 1]);//交换物品的序号
- }
- }
- }
-
- for (int k = 0; w[k] <= c; k++)
- {
- v[k] = true;
- c = c - w[k];//船的剩余装载量
- }
- }
- int main()
- {
- float c;//表示船的最大载重和物品个数
- int n;//物品个数
- cout << "请依次输入船的最大载重和物品个数:" << endl;
- cin >> c >> n;
- vector<float> w(n);//存放物品的重量
- vector<int> t(n);;//存放物品的下标
- vector<bool> v(n);//记录物品是否装入船中
- cout << "请依次输入物品重量:" << endl;
- for (int i = 0; i < n; i++)//初始化物品信息
- {
- cin >> w[i];
- t[i] = i;
- v[i] = false;
- }
-
- Loading(c,w,t,v);
- cout << "装入了:" << endl;
- for (int i = 0; i < w.size(); i++)//输出装入的物品
- {
- if (v[i] == true)
- cout << t[i] << "号物品," << "重量为:" << w[i] << endl;
- }
- return 0;
- }
- //测试数据
- //30 8
- //4 10.5 7.8 4.9 5.1 3.3 4.6 3.2
-
-
- //结果
- //装入了:
- //7号物品,重量为:3.2
- //5号物品,重量为:3.3
- //0号物品,重量为:4
- //6号物品,重量为:4.6
- //3号物品,重量为:4.9
- //4号物品,重量为:5.1
背包最大容量为30,在依次选择物品2、10、6、3、5后,背包最大价值达到69,背包剩余容量为,只能装8号物品的,此时背包最大价值为
- void CompletePack(int _bagW,int n,struct goods*ps)
- {
- double sum = 0;//背包总价值
- for (int i = 0;i<n; i++)
- {
- if (_bagW >ps[i].w)//背包容量大于物品重量
- {
- ps[i].c = 1;
- sum =sum+ ps[i].v;
- _bagW = _bagW - ps[i].w;//剩余背包容量
- }
- else//背包容量小于物品重量
- {
- ps[i].c = (double)_bagW / (double)ps[i].w;//装入物品的比例(必须要强制转换)
- sum =sum+ps[i].c *ps[i].v;
- break;
- }
- }
- cout << "背包最大价值:" << sum << endl;
- }
- #include<iostream>
- #include<algorithm>
- #include<iomanip>//setw的头文件
- using namespace std;
- #define MAX 100//物品数量最多为100
- struct goods
- {
- int n;//物品编号
- int w;//物品重量
- int v;//物品价值
- double p;//物品性价比
- double c;//记录装入物品的比例(如果物品完全放入背包,则c=1;不放入,c=0)
- }g[MAX];
-
- void Init(int n, struct goods*ps);//初始化物品信息
- bool cmp(struct goods a,struct goods b);//比较
- void CompletePack(int _bagW,int n,struct goods*ps);
- void print(int n, struct goods* ps);//遍历
-
- void Init(int n, struct goods*ps)//初始化物品信息
- {
- cout << "请依次输入物品的重量和价值:" << endl;
- for (int i = 0; i < n; i++)
- {
- ps[i].n = i;//物品编号
- cin >>ps[i].w >> ps[i].v;//初始化物品重量和价值
- ps[i].p = (double)ps[i].v / (double)ps[i].w;//性价比
- ps[i].c = 0;//都没有放入背包
- }
- }
-
- bool cmp(struct goods a,struct goods b)//比较
- {
- return a.p > b.p;//根据物品单位价值从大到小排序
- }
- void CompletePack(int _bagW,int n,struct goods*ps)
- {
- double sum = 0;//背包总价值
- for (int i = 0;i<n; i++)
- {
- if (_bagW >ps[i].w)//背包容量大于物品重量
- {
- ps[i].c = 1;
- sum =sum+ ps[i].v;
- _bagW = _bagW - ps[i].w;//剩余背包容量
- }
- else//背包容量小于物品重量
- {
- ps[i].c = (double)_bagW / (double)ps[i].w;//装入物品的比例(必须要强制转换)
- sum =sum+ps[i].c *ps[i].v;
- break;
- }
- }
- cout << "背包最大价值:" << sum << endl;
- }
- void print(int n, struct goods* ps)
- {
- for (int i = 0; i < n; i++)
- {
- if (ps[i].c != 0)
- {
- if (ps[i].c == 1)
- cout << "物品" << ps[i].n << setw(20) << "价值为:" << ps[i].v << endl;
- else
- cout << "物品" << ps[i].n << "装入了" << ps[i].c <<setw(8)<< " 价值为:" << ps[i].v << endl;
- }
- }
- }
-
- int main()
- {
- int bagW, n;//背包最大容量和物品数量
- cout << "请依次输入物品重量和物品数量:" << endl;
- cin >> bagW >> n;
- Init(n,g);//初始化物品信息
- cout << endl<<endl ;
- sort(g, g + n, cmp);//排序
- CompletePack(bagW,n, g);
- print(n, g);
- return 0;
- }
-
- //测试数据
- // 背包容量30 物品数量10
- //4 3
- //2 8
- //9 18
- //5 6
- //5 8
- //8 20
- //5 5
- //4 6
- //5 7
- //5 15
-
- //结果
- //背包最大价值:70.5
- //物品1 价值为:8
- //物品9 价值为:15
- //物品5 价值为:20
- //物品2 价值为:18
- //物品4 价值为:8
- //物品7装入了0.25 价值为:6
- #include<iostream>
- #include <iomanip>//setw的头文件
- using namespace std;
- #define MAX 20//物品数量最多为20
- class goods
- {
- private:
- int number;//物品编号
- int weight;//物品重量
- double value;//物品价值
- double percentage;//物品性价比
- double choice;//记录装入物品的比例(如果物品完全放入背包,则choice=1;不放入,choice=0)
- public:
- goods() { ; }
- goods(int _n,int _w, double _v, double _p, double _c)//构造函数
- {
- this->number = _n;
- this->weight = _w;
- this->value = _v;
- this->percentage = _p;
- this->choice = _c;
- }
- //~goods();//析构函数
-
- //获取私有成员
- int getn();//获取私有成员number
- int getw();//获取私有成员weight
- double getv();//获取私有成员value
- double getp();//获取私有成员percentage
- double getc();//获取私有成员choice
-
- //修改私有成员
- void setn(int _n);//修改私有成员的number
- void setw(int _w);
- void setv(double _v);
- void setp(double _p);
- void setc(double _c);
- };
-
- int goods::getn()
- {
- return number;
- }
- int goods::getw()//获取私有成员weight
- {
- return weight;
- }
- double goods::getv()
- {
- return value;
- }
- double goods::getp()
- {
- return percentage;
- }
- double goods::getc()
- {
- return choice;
- }
-
- void goods::setn(int _n)
- {
- number = _n;
- }
- void goods::setw(int _w)
- {
- weight = _w;
- }
- void goods::setv(double _v)
- {
- value = _v;
- }
- void goods::setp(double _p)
- {
- percentage = _p;
- }
- void goods::setc(double _c)
- {
- choice = _c;
- }
- int main()
- {
- int bagW, n;//背包最大容量和物品数量
- cout << "请依次输入背包容量和物品数量:" << endl;
- cin >> bagW >> n;
- //goods *g=new goods[MAX];
- goods g[MAX];
- cout << "请依次输入物品重量和物品价值:" << endl;
- for (int i = 0; i < n; i++)
- {
- int _n,_w,_c;//物品编号,物品重量,物品是否放入了背包
- double _v, _p;//物品价值,物品性价比
- cin >> _w >> _v;
- _p = _v / _w;//性价比
- _n = i;//编号
- _c = 0;//是否放入了背包
-
- goods gg(_n, _w, _v, _p, _c);
- g[i] = gg;
- }
-
-
- for (int i = 0; i <= n - 1; i++)//简单选择排序(按照性价比从大到小)
- {
- double max = g[i].getp();
- int k = i;//保存最大性价比的物品下标
- for (int j = i; j < n; j++)
- {
- if (max < g[j].getp())
- {
- max = g[j].getp();
- k = j;
- }
- }
- swap(g[i], g[k]);
- }
-
- double sum = 0;//背包总价值
- for (int i = 0; i < n; i++)
- {
- if (bagW > g[i].getw())//背包容量大于物品重量
- {
- g[i].setc(1);//物品全部装入背包
- sum += g[i].getv();//背包价值增加
- bagW = bagW - g[i].getw();//剩余背包容量
- }
- else//背包容量大于物品重量
- {
- double x = double(bagW) / double(g[i].getw());
- g[i].setc(x) ;//装入物品的比例
- sum += g[i].getc() * g[i].getv();
- break;
- }
- }
-
- cout << "物品的最大价值为:" << sum << endl;
- for (int i = 0; i < n; i++)
- {
- if (g[i].getc() != 0)
- {
- if (g[i].getc() == 1)
- cout << "物品" << g[i].getn() << setw(20) << "价值为:" << g[i].getv() << endl;
- else
- cout << "物品" << g[i].getn() << "装入了" << g[i].getc() <<setw(8)<< " 价值为:" << g[i].getv() << endl;
- }
- }
- return 0;
- }
-
- //测试数据
- //30 10
- //4 3
- //2 8
- //9 18
- //5 6
- //5 8
- //8 20
- //5 5
- //4 6
- //5 7
- //5 15
-
- //结果
- //物品的最大价值为:70.5
- //物品1 价值为:8
- //物品9 价值为:15
- //物品5 价值为:20
- //物品2 价值为:18
- //物品4 价值为:8
- //物品7装入了0.25 价值为:6
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。