背包问题扩展三.cpp

来自「这是经典的背包问题」· C++ 代码 · 共 42 行

#define MAX 200
#include<iostream>
#include<cstdio>
using namespace std;

struct Item{                                                 //建立结构数组，包含两个数据：物品的重量以及其单位价值
	double weight, value;
}item[MAX], tmp;

int main(){
	double capacity, v, totalvalue=0; 
	int s, i, j;
	cin >> capacity >> s;                                    //s变量表示物品的种数
	for (i=1; i <= s; i++){
		cin >> item[i].weight >> v;
		item[i].value = v/item[i].weight;
	}
	
	for (i=1; i <= s; i++){                                  //采用选择排序法，对物品的单位价值进行排序
		for (j=1; j <= i; j++){
			if (item[j].value < item[i].value){
				tmp=item[j];
				item[j]=item[i];
				item[i]=tmp;
			}
		}
	}
	
	for (i=1; (capacity != 0) && (i <= s); i++){
		if (item[i].weight <= capacity ){                    //对于第i个物品，背包剩下的容积尚能容纳其重量  
			capacity -= item[i].weight;                      //则将背包容积减少item[i].weight
			totalvalue += item[i].value*item[i].weight;      //总价值增加item[i].value
		}
		else{
			totalvalue += item[i].value*capacity;            //若不能，则将第i个物品的单位价值直接与背包剩下的容积相乘
			capacity=0;                                      //同时将剩余容积设为零
		}
	}
	printf("%.2f\n",totalvalue);
	return 0;
}