?? koudai2.cpp
字號:
// 我保證這次作業是我個人獨立完成沒有抄襲他人作業和代碼
#include<iostream>
#include<string>
using namespace std;
// 定義一個結構 記錄數據
struct packet
{
int value; // 記錄每個物品的價值
int size; // 記錄每一個物品的大小
}temp[100]; // 定義最多有100個物品
// compare 函數
// 按照 單位大小所含有的價值進行排列
int compare(const void *a ,const void *b)
{
return ((packet *)b)->value*((packet *)a)->size - ((packet * )b)->size*((packet *)a)->value;
}
int msize,num;// 記錄口袋的最大可成放的 msize 已經所有物品的數目
// 定義一個函數 用于設置數據
void set()
{
cout<<"please input the totle size of the bag"<<endl;
cin>>msize;
cout<<"please input the number of the bags"<<endl;
cin>>num;
cout<<"please input the size and the value of each bag"<<endl;
for(int i=0;i<num;i++)
{
cin>>temp[i].size>>temp[i].value;
}
}
// 主要的計算函數
void funtion()
{
int l = msize; //口袋當前所能夠容納的大小
double c=0; // 當前口袋內物品的總價值
// 現比較一下
qsort(temp,num,sizeof(packet),compare);
for(int i=0;i<num;i++)
{
if(temp[i].size<= l) // 如果口袋可以成放 temp[i]時 就操作
{
c+=temp[i].value; // 總價值增加
l=l-temp[i].size; // 相當口袋的大小也要減小
}
// 下面是利用物品的可分性 如果口袋的可容量已經小于temp[i]
// 就要對其進行分割 取出l 大小的物品
else
{
c+=temp[i].value*l/temp[i].size;
l=0;
}
if(l==0) break; //如果口袋已經裝滿了 就要結束了
}
cout<<c<<endl;
}
// 在主函數中分別調用兩個函數
void main()
{
set();
funtion();
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -