7-25 部分背包 (10 分)
给定 N 种物品和一个背包。物品 i 的重量是 W i ，价值为 V i ；背包的容量为 V。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品，对每种物品可以选择：全部装入或装入部分，且不能重复装入。输入数据的第一行分别为：背包的容量 V，物品的个数 N。接下来的 N 行表示 N 个物品的重量和价值。输出为最大的总价值。
输入格式:
第一行连个整数，分别是V和N(<=1000) 接下来N行，每行分别为 W i 和 V i
输出格式:
输出为最大的总价值（保留两位小数）
输入样例:
15 4 3 5 4 6 5 7 7 12
输出样例:
24.40
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
int v,n;
double maxx=0.0;
cin>>v>>n;
double shangpin[n][3];
for(int i=0;i<n;i++){
cin>>shangpin[i][0]>>shangpin[i][1];
shangpin[i][2]=shangpin[i][1]/shangpin[i][0];
//cout<<shangpin[i][2];
}
for(int i=0;i<n;i++){
int max=i;
for(int j=i+1;j<n;j++){
if(shangpin[j][2]>shangpin[max][2]){
max=j;
}
}
double temp0,temp1,temp2;
temp0=shangpin[i][0];
temp1=shangpin[i][1];
temp2=shangpin[i][2];
shangpin[i][0]=shangpin[max][0];
shangpin[i][1]=shangpin[max][1];
shangpin[i][2]=shangpin[max][2];
shangpin[max][0]=temp0;
shangpin[max][1]=temp1;
shangpin[max][2]=temp2;
// cout<<shangpin[i][0]<<" "<<shangpin[i][1]<<" "<<shangpin[i][2]<<endl;
}
for(int i=0;i<n;i++){
if(shangpin[i][0]<v){
maxx+=shangpin[i][1];
v-=shangpin[i][0];
}
else{
maxx+=shangpin[i][2]*v;
}
}
printf("%.2lf",maxx);
}