HDU 2111 Saving HDU(贪心,01背包)

2023-11-02 08:38
文章标签 贪心 01 背包 hdu saving 2111

本文主要是介绍HDU 2111 Saving HDU(贪心,01背包),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Problem Description
话说上回讲到海东集团面临内外交困,公司的元老也只剩下XHD夫妇二人了。显然,作为多年拼搏的商人,XHD不会坐以待毙的。
  一天,当他正在苦思冥想解困良策的时候,突然想到了自己的传家宝,那是公司成立的时候,父亲作为贺礼送来的一个锦囊,徐父当时交代,不到万不得已的时候,不要打开它。“现在不正是最需要的时候吗?”,一边想,XHD一边找到了这个精心保管的锦囊,打开一看,里面只有一句话“杭城北麓千人洞有宝”。
  二话不说,XHD拿起一个大口袋就出发了,这个千人洞他是知道的,小的时候,爸爸曾经带他来过这个隐蔽的路口,并告诉他,这是千人洞。他现在才明白爸爸当初这句话的含义。
  尽管有点印象,XHD还是花了很大的精力才找到这个异常隐蔽的洞口,走进一看,几乎惊呆了,真的是眼花缭乱!不过尽管宝贝的种类不少,但是每种宝贝的量并不多,当然,每种宝贝单位体积的价格也不一样,为了挽救HDU,现在请你帮忙尽快计算出来XHD最多能带回多少价值的宝贝?(假设宝贝可以分割,分割后的价值和对应的体积成正比)

Input
输入包含多个测试实例,每个实例的第一行是两个整数v和n(v,n<100),分别表示口袋的容量和宝贝的种类,接着的n行每行包含2个整数pi和mi(0<pi,mi<10),分别表示某种宝贝的单价和对应的体积,v为0的时候结束输入。

Output
对于每个测试实例,请输出XHD最多能取回多少价值的宝贝,每个实例的输出占一行。

Sample Input
  
2 2 3 1 2 3 0

Sample Output
5经过锦囊相助,HDU会脱离危机吗?

欲知后事如何,且听下回分解——

题意分析:

此题为01背包问题,也就是贪心的思想。

题意为输入v,n(v为口袋的容量,n为宝贝的种类)

pi[0...n]为某种物品的单价,mi[0...n]为对应的体积

样例为

2 2

3 1

2 3 -> 5

第一种解法:因为价格与体积是一一对应的,所以要用结构体。对每个变量按照价格为关键字进行排序,每次装包都要先装价格大的,这样也就保证了最终总价值是最大的。这种局部最优保证总部最优的思想,也是贪心。

<pre name="code" class="cpp">
<pre name="code" class="cpp">#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>#define INF (INT_MAX / 10)
#define clr(arr, val) memset(arr, val, sizeof(arr))
#define pb push_back
#define sz(a) ((int)(a).size())using namespace std;
typedef set<int> si;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef long long ll;const double esp = 1e-5;#define N 100+10struct Node{int pi;  //单位体积的价格 int mi; //对应价格的体积 
}a[N];bool cmp(Node a,Node b)   //注意此时传入的参数类型为node结构体型,而不是int型 
{return a.pi>b.pi;   //以单价为关键字符,由大到小排序 
}
int main()
{int v,n;while(scanf("%d",&v)!=EOF&&v){scanf("%d",&n);int sum=0,t=0,flag=0;for(int i=0;i<n;i++)scanf("%d %d",&a[i].pi,&a[i].mi);sort(a,a+n,cmp);for(int i=0;i<n;i++){for(int j=a[i].mi;j>0;j--)  //每种物品也是有自己的体积的,加了一回就少一个了 ,所以这一步也是要控制的 {if(t<v)    //t为当前已装入的重量 {t++; sum+=a[i].pi;}else{flag=1;break;}}if(flag)break;}printf("%d\n",sum); }return 0;
}<strong><span style="font-size:18px;">
</span></strong>
接下来是普通的不用结构体,就是简单的排序后判断的同样AC的代码:

<pre name="code" class="cpp">#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>#define INF (INT_MAX / 10)
#define clr(arr, val) memset(arr, val, sizeof(arr))
#define pb push_back
#define sz(a) ((int)(a).size())using namespace std;
typedef set<int> si;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef long long ll;const double esp = 1e-5;#define N 100+10
int main()
{int mi[N],pi[N];int tot,v,n;while(scanf("%d",&v)!=EOF&&v){scanf("%d",&n);tot=0;for(int i=0;i<n;i++)scanf("%d%d",&pi[i],&mi[i]);//利用冒泡法对单价进行排序 for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(pi[i]<pi[j]){int t=pi[i];pi[i]=pi[j];pi[j]=t;t=mi[i];mi[i]=mi[j];mi[j]=t;}}}for(int i=0;i<n;i++){if(v>=mi[i]){tot+=pi[i]*mi[i];v-=mi[i];}else{tot+=pi[i]*v;  //如果最高价格的体积小于总体积,那肯定是让总体积直接乘最高价格 break;}} printf("%d\n",tot);}return 0;
}


 
 
 
 

这篇关于HDU 2111 Saving HDU(贪心,01背包)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/329417

相关文章

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s