ACM暑假集训总结1百度之星第三场Discount01背包问题

77 阅读 0 评论 51 点赞

我是靠谱客的博主怕孤单蓝天，最近开发中收集的这篇文章主要介绍ACM暑假集训总结1百度之星第三场Discount01背包问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

百度之星第三场Discount

题目描述
学皇来到了一个餐馆吃饭。他觉得这家餐馆很好吃，于是就想办个会员。

一共有 nn 种会员充值卡套餐，假设学皇这餐饭的消费为 aa 元，选择第 ii 种套餐，需要充值 b[i] * ab[i]∗a 的钱，这次吃饭可以打 c[i]times 10c[i]×10 折，由充值的钱支付（即这次吃饭只需要从充值金额中扣除 atimes c[i]a×c[i] 元）。以后用剩余的充值的钱吃饭不再打折。

请问学皇应该选择哪个套餐（必须选择恰好一个套餐），使得优惠的比例最大？

优惠比例的定义是把充的钱用完以后，(本来应该付的钱 - 实际付的钱) / 本来应该付的钱。在这个题目里，实际付的钱就是这次充值的花费
Input
第一行一个整数 test(1 leq test leq 100)test(1≤test≤100) 表示数据组数。

对于每组数据，第一行一个正整数 n(1 leq n leq 100)n(1≤n≤100) 表示套餐的数目。

接下来 nn 行，每行一个正整数 b[i](1 leq b[i] leq 100)bi 和一个小数 c[i](0 leq c[i] leq 1c[i](0≤c[i]≤1，c[i]c[i] 最多包含两位小数)。

Output
对于每组数据，输出一个五位小数表示最大的优惠比例。如果小数点后超过五位，四舍五入到五位。

Sample Input
1
2
2 0.5
3 0.1
Sample Output
Copy
0.23077

样例解释
对于第一种套餐，优惠比例为 0.5a / (2a + 0.5a） = 0.2；
对于第二种套餐，优惠比例为 0.9a / (3a + 0.9a） = 9 / 39；

解法一

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
int main()
{
	int n;cin>>n;double sum[200]={0.00000};double a[200],b[200];
	while(n--){
		int m;cin>>m;
		for(int i=0;i<m;i++){
			cin>>a[i]>>b[i];
			sum[i]=(1.00000-b[i])/(a[i]+(1.00000-b[i]));
			cout<<sum[i]<<endl;
	        cout<<i<<endl; 
		}
		sort(sum,sum+m);
		printf("%.5lf",sum[m-1]);
		
	} 
	return 0;
}

求最小！！！

解法二

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define debug(x) cerr << #x << " = " << x << 'n';
#define pll pair <ll, ll>
#define fir first
#define sec second

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

int main() {
  int T = read();
  while (T--) {
    int n = read();
    double p = 0.0;
    while (n--) {
      int x;
      double pp;
      scanf("%d%lf", &x, &pp);
      pp = 1 - pp;
      p = max(p, pp / (x + pp));
    }
    printf("%.5lfn", p); 
  }
  return 0;
}

01背包问题

01背包的题目描述的标志

描述： n件物品，容量为v，第i件物品的重量为w[i]，价值为v[i],求怎么装可以使背包装的价值之和最大

理解：每件物品只能拿一次，每件物品可以选择拿或不拿，所以我们从前i件物品开始考虑拿或者不拿；

拿第i件物品：背包总价值就是第i件价值加上前i-1价值的总和；用表达式表示的话就是总价值=v[i]+前i-1的价值总和

这里我们设f[i][j]表示前i件物品放在容量为j的最大价值

不拿第i件物品：背包的总价值就很简单计算了，就直接是前i-1件物品的总价值了
因为每次拿与不拿有一个关键因素就是当前拿的物品是否超过当前背包剩余的容量，所以在循环部分可以继续改进

for (int i = 1; i <= n; i++)
    for (int j = V; j >= w[i]; j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);

洛谷2925

题目描述
农民john面临一个很可怕的事实，因为防范失措他存储的所有稻草给澳大利亚蟑螂吃光了，他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前，john拉着他的马车到农民Don的农场中买一些稻草给奶牛过冬。已知john的马车可以装的下C(1 <= C <=50,000)立方的稻草。
农民Don有H(1 <= H <= 5,000)捆体积不同的稻草可供购买，每一捆稻草有它自己的体积(1 <= V_i <= C)。面对这些稻草john认真的计算如何充分利用马车的空间购买尽量多的稻草给他的奶牛过冬。
现在给定马车的最大容积C和每一捆稻草的体积Vi，john如何在不超过马车最大容积的情况下买到最大体积的稻草？他不可以把一捆稻草分开来买。

输入输出格式
输入格式：
第一行两个整数，分别为C和H
第2…H+1行:每一行一个整数代表第i捆稻草的体积Vi

输出格式：
一个整数，为john能买到的稻草的体积

输入输出样例
输入样例#1：
7 3
2
6
5

输出样例#1：
7

 #include<bits/stdc++.h>
    using namespace std;
    int f[111111];
    int main()
    {
        int n,m,i,j,a[111111];
        cin>>m>>n;
        for (i=1;i<=n;i++) scanf("%d",&a[i]);
        for (i=1;i<=n;i++)
        {
            for (j=m;j>=a[i];j--)
            f[j]=max(f[j],f[j-a[i]]+a[i]);
            if (f[m]==m) {printf("%d",m); return 0;}//优化，如果已经达到最好的结果（装满），就直接退掉
        }
        printf("%d",f[m]);
}