P2240 【深基12.例1】部分背包问题

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N \le 100)N(N≤100) 堆金币，第 ii 堆金币的总重量和总价值分别是 m_i,v_i(1\le m_i,v_i \le 100)m**i,v**i(1≤m**i,v**i≤100)。阿里巴巴有一个承重量为 T(T \le 1000)T(T≤1000) 的背包，但并没办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

输入格式

第一行两个整数 N、T

接下来 N 行，每行两个整数 m_i,v_im**i​,v**i​

输出格式

一个整数表示答案，输出两位小数

输入输出样例

输入 #1

4 50

10 60

20 100

30 120

15 45

输出 #1

240.00

//P2240 【深基12.例1】部分背包问题

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int findmax(double*,int);

int main()

{

	int mass[102];

	int money[102];

	double rate[102];

	int number,mass_sum,max,count;//count用于避开背包空间没用完的情况

	double sum=0.0;

	int i=0;

	scanf("%d%d",&number,&mass_sum);

	for(i=0;i<number;i++){

		scanf("%d%d",&mass[i],&money[i]);

		rate[i]=(double)money[i]/(double)mass[i];//坑点1：强制转换，否则无法AC

	}

	count=number;

	while(mass_sum>0&&count>0){//坑点2：背包空间没用完，所以需要加count判断条件

		max=findmax(rate,number);

		if(mass_sum-mass[max]>=0){

			mass_sum-=mass[max];

			sum+=money[max];

		}

		else{

			sum=sum+mass_sum*rate[max];

			mass_sum=0;

			break;

		}

		count--;

		rate[max]=0.0;

	}

	printf("%.2lf",sum);

	return 0;

}

int findmax(double* rate,int num){

	int i=0,tag=0;

	double max=0.0;

	for(i=0;i<num;i++){

		if((rate[i]-max)>=1e-6){

			max=rate[i];

			tag=i;

		}

	}

	return tag;

}

坑点两个：

一个是强制转换的坑，可过数据为0个，第二个是背包空间没用完，可过80%的数据

//强制转换具体影响

#include <stdio.h>

int main()

{

	int a=5;int b=2;

	double c,d;

	c=a/b;

	d=(double)a/(double)b;

	printf("%lf %lf",c,d);

	return 0;

}

输出

2.000000 2.500000