HPU Summer Day 15
今天主要讲了01背包，完全背包，多重背包的相关东西。不太好理解，题也有点难。关于背包东西还有很多，慢慢学吧。
Bone Collector
Description:
涂奥最近迷上了吃鸡，房间有n个配件，每个配件有c(c<=1e3)的重量和v(v<=1e3)的价值，哇，涂奥捡了一个2级包，容量为s，所以涂奥最多当多肥的快递员呢？
Input
输入的第一行是T, 表示有一共要打T场比赛.
每组数据由三行组成.
第1行包含两个整数n和s 第2行包含n个整数, 表示每一个配件的价值. 第3行包含n个整数, 表示每个配件的重量.
Output
对每一组数据, 输出涂奥可以多肥.
Sample Input
1
10 10
1 3 5 7 9 11 13 15 17 19
19 17 15 13 11 9 7 5 3 1
Sample Output
51
Problem solving:
跟昨天那道题一样，不过就是换了描述。
提议就是给定你容量，然后告诉你每个物品的价值和体积，求你能拿到的最大的价值。
01背包问题，直接套板子即可
Code:
#include<bits/stdc++.h>
using namespace std;
const int tx=1e6;
int m[tx],M[tx],dp[tx];
int main()
{
int t,n,s;
cin>>t;
while(t--)
{
cin>>n>>s;
for(int i=0;i<n;i++) cin>>m[i];
for(int i=0;i<n;i++) cin>>M[i];
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
{
for(int j=s;j>=M[i];j--)
{
dp[j]=max(dp[j],dp[j-M[i]]+m[i]);
}
}
cout<<dp[s]<<endl;
}
}饭卡
Description:
电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
Input
多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。
Output
对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。
Sample Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
Sample Output
-45
32
Problem solving:
题意就是让你尽可能多的花掉自己的钱，求余额。有一个特殊规定就是如果当前余额大于等于5，能买任何的菜，但是一旦n小于5，就什么都不能买了。
也是一道01背包的问题，这里还有一点贪心的感觉就是，为了最后能达到的是最小的余额，我们拿5元出来买最贵的菜。然后就是背包，背包容量是n-5，直接套板子求出n-5的容量下能花费最多钱的情况。
最后输出的时候减去最大的花费和最贵的菜即可。
但是还有一点就是输入的n就有可能是小于5的。这时直接输出n就行。
Code:
#include<bits/stdc++.h>
using namespace std;
const int tx=1005;
int m[tx],dp[tx];
int main()
{
int t,n;
while(cin>>t&&t)
{
memset(dp,0,sizeof(dp));
for(int i=0;i<t;i++) cin>>m[i];
cin>>n;
if(n<5)
{
cout<<n<<endl;
continue;
}
sort(m,m+t);
for(int i=0;i<t-1;i++)
for(int j=n-5;j>=m[i];j--)
{
dp[j]=max(dp[j],dp[j-m[i]]+m[i]);
}
cout<<n-dp[n-5]-m[t-1]<<endl;
}
}CD
Description:
PDF题面:戳我戳我
You have a long drive by car ahead. You have a tape recorder, but unfortunately your best music is on
CDs. You need to have it on tapes so the problem to solve is: you have a tape N minutes long. How
to choose tracks from CD to get most out of tape space and have as short unused space as possible.
Assumptions:
• number of tracks on the CD does not exceed 20
• no track is longer than N minutes
• tracks do not repeat
• length of each track is expressed as an integer number
• N is also integer
Program should find the set of tracks which fills the tape best and print it in the same sequence as
the tracks are stored on the CD
Input
Any number of lines. Each one contains value N, (after space) number of tracks and durations of the
tracks. For example from first line in sample data: N = 5, number of tracks=3, first track lasts for 1
minute, second one 3 minutes, next one 4 minutes
Output
Set of tracks (and durations) which are the correct solutions and string ‘sum:’ and sum of duration
times.
Sample Input
5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2
Sample Output
1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45
Problem solving:
这道题的意思就是给你一个数，这个就是背包容量然后给你n个数，问你这n个数怎么放能使背包容量最小，并输出这个方法。
简单的01背包问题。不简单的输出方法。
在每次dp查找最优情况的时候进行标记，最后根据标记输出，并且题目要求的输出是出现在前面的就输出在前面，最后还有一点小优化，可以看一下代码注释理解。
关于这个输出路径，我也不是理解的很清楚，但是很关键的要理解的一点就是dp[j]这个数组的含义。也就是01背包中dp[i][j]的意思:从前i-1个物品中，选出来总重量不超过j的物品时，总价值的最大值
Code:
#include<bits/stdc++.h>
using namespace std;
int n,m,num;
const int maxn=10005;
int a[maxn],dp[maxn],flag[maxn][maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
while(cin>>n>>m)
{
for(int i=0;i<m;i++) cin>>a[i];
memset(flag,0,sizeof(flag));
memset(dp,0,sizeof(dp));
for(int i=m-1;i>=0;i--)//这里倒序主要是在输出的时候方便
{
for(int j=n;j>=a[i];j--)
{
if(dp[j]<dp[j-a[i]]+a[i])//选上了a[i]的情况
{
dp[j]=dp[j-a[i]]+a[i];
flag[i][j]=1;//进行标记
}
}
}
for(int i=0,j=n;i<m;i++)
{
if(flag[i][j])//标价到的就输出
{
cout<<a[i]<<" ";
j-=a[i];
}
}
cout<<"sum:"<<dp[n]<<endl;
}
}Piggy-Bank
Description:
在 ACM 能够开展之前，必须准备预算，并获得必要的财力支持。该活动的主要收入来自于 Irreversibly Bound Money (IBM)。思路很简单。任何时候，某位 ACM 会员有少量的钱时，他将所有的硬币投入到小猪储钱罐中。这个过程不可逆，因为只有把小猪储钱罐打碎才能取出硬币。在足够长的时间之后，小猪储钱罐中有了足够的现金，用于支付 ACM 活动所需的花费。
但是，小猪储钱罐存在一个大的问题，即无法确定其中有多少钱。因此，我们可能在打碎小猪储钱罐之后，发现里面的钱不够。显然，我们希望避免这种不愉快的情况。唯一的可能是，称一下小猪储钱罐的重量，并尝试猜测里面的有多少硬币。假定我们能够精确判断小猪储钱罐的重量，并且我们也知道给定币种的所有硬币的重量。那么，我们可以保证小猪储钱罐中最少有多少钱。
你的任务是找出最差的情形，即判断小猪储钱罐中的硬币最少有多少钱。我们需要你的帮助。不能再贸然打碎小猪储钱罐了！
输入
输入包含 T 组测试数据。输入文件的第一行，给出了 T 的值。
对于每组测试数据，第一行包含 E 和 F 两个整数，它们表示空的小猪储钱罐的重量，以及装有硬币的小猪储钱罐的重量。两个重量的计量单位都是 g (克)。小猪储钱罐的重量不会超过 10 kg (千克)，即 1 <= E <= F <= 10000 。每组测试数据的第二行，有一个整数 N (1 <= N <= 500)，提供了给定币种的不同硬币有多少种。接下来的 N 行，每行指定一种硬币类型，每行包含两个整数 P 和 W (1 <= P <= 50000，1 <= W <=10000)。P 是硬币的金额 (货币计量单位)；W 是它的重量，以 g (克) 为计量单位。
输出
对于每组测试数据，打印一行输出。每行必须包含句子 “The minimum amount of money in the piggy-bank is X.” 其中，X 表示对于给定总重量的硬币，所能得到的最少金额。如果无法恰好得到给定的重量，则打印一行 “This is impossible.” 。
示例输入
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
示例输出
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
Problem solving:
这道题的意思是给你一个存钱罐的初始和末状态的质量，然后给定你每种硬币的质量和价值。要求这个存钱罐是否存在着能正好放满硬币的情况，如果有求出最小的情况。
每个硬币可以挑选任意次，所以这是一道完全背包的题。套板子就行，注意我们要求最小值，所以初始化成一个极大值，然后在dp的过程中取min。
还有一点就是dp[0]一定要初始化为0，因为这里我们dp[i]表示的就是在i的空间下，能放人的最小的硬币的值。空间为0即不能再放硬币了，所以价值就是0了。
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int p[505],w[505],dp[10005];
const int INF = 0x3f3f3f3f;
int main()
{
int t,s,e,n,cs;
cin>>t;
while(t--)
{
cin>>s>>e>>n;
cs=e-s;
for(int i=0;i<=cs;i++) dp[i]=INF;
for(int i=0;i<n;i++) cin>>p[i]>>w[i];
dp[0]=0;
for(int i=0;i<n;i++)
{
for(int j=w[i];j<=cs;j++)
{
dp[j]=min(dp[j],dp[j-w[i]]+p[i]);
}
}
if(dp[cs]!=INF)
cout<<"The minimum amount of money in the piggy-bank is "<<dp[cs]<<".";
else cout<<"This is impossible.";
puts("");
}
}Dividing coins
Description:
PDF题面：戳我戳我
It’s commonly known that the Dutch have invented copper-wire. Two Dutch men were fighting over
a nickel, which was made of copper. They were both so eager to get it and the fighting was so fierce,
they stretched the coin to great length and thus created copper-wire.
Not commonly known is that the fighting started, after the two Dutch tried to divide a bag with
coins between the two of them. The contents of the bag appeared not to be equally divisible. The Dutch
of the past couldn’t stand the fact that a division should favour one of them and they always wanted
a fair share to the very last cent. Nowadays fighting over a single cent will not be seen anymore, but
being capable of making an equal division as fair as possible is something that will remain important
forever...
That’s what this whole problem is about. Not everyone is capable of seeing instantly what’s the
most fair division of a bag of coins between two persons. Your help is asked to solve this problem.
Given a bag with a maximum of 100 coins, determine the most fair division between two persons.
This means that the difference between the amount each person obtains should be minimised. The
value of a coin varies from 1 cent to 500 cents. It’s not allowed to split a single coin.
Input
A line with the number of problems n, followed by n times:
• a line with a non negative integer m (m ≤ 100) indicating the number of coins in the bag
• a line with m numbers separated by one space, each number indicates the value of a coin.
Output
The output consists of n lines. Each line contains the minimal positive difference between the amount
the two persons obtain when they divide the coins from the corresponding bag.
Sample Input
2
3
2 3 5
4
1 2 4 6
Sample Output
0
1
Problem solving:
这道题的意思就是给你n个硬币，让你分成两堆，求所有分法中两堆价值差值最小的情况。
这道题乍一看以为是要贪心，但是WA了。
然后想到今天讲的是背包诶，然后脑子里灵光一现(去百度了一下)，想到可以以硬币的总价值的一半为背包容量进行01背包的处理。假设总价值为s，这时我们求出的dp[s/2]就是分成差值最小的两堆中的其中一堆，然后另一堆的价值就是s-sp[s/2],两堆价值的差值就是s-2*dp[s/2]
Code:
#include<bits/stdc++.h>
using namespace std;
const int tx=1e5+10;
int m[tx],dp[tx];
int main()
{
int n,t;
cin>>n;
while(n--)
{
cin>>t;
memset(dp,0,sizeof(dp));
int sum=0;
for(int i=0;i<t;i++) cin>>m[i],sum+=m[i];
for(int i=0;i<t;i++)
{
for(int j=sum/2;j>=m[i];j--)
{
dp[j]=max(dp[j],dp[j-m[i]]+m[i]);
}
}
cout<<sum-dp[sum/2]-dp[sum/2]<<endl;
}
return 0;
}Robberies
Description:
可怜的POIUYTREWQ最近想买下dota2的商品，但是手头缺钱。他想起了之前看过的一部大片，觉得抢银行也许是个不错的选择。他认为，坏人被抓是因为没有预先规划。于是他在之前的几个月对各大银行进行了一次评估； 评估内容包括安全性和可盗窃金额： 他想知道在在某个风险系数下可以偷窃的最大金额
Input
第一行给出了一个整数T, 表示有T组测试数据. 对于每一组数据，第一行给出了一个浮点数P, 表示POIUYTREWQ允许被抓的最大概率, 和一个整数N，表示他计划去抢劫的N个银行. 接下来N行, 每行给出一个整数数Mj和浮点数Pj.
抢劫银行 j 可获得 Mj 百万美金, 被抓的概率是 Pj .
Output
对于每组数据，每行输出一个整数，表示POIUYTREWQ在被抓概率小于P的情况下，可抢到的最多的金钱。
Notes and Constraints
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0.0 <= Pj <= 1.0
你可以认为每家银行都是独立的。
Sample Input
3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05
Sample Output
2
4
6
Problem solving:
这道题就是先给你一个实数代表这个可怜的孩子能允许的最大的被抓的概率，意思就是你被抓的概率不能超过这个值。然后给你n个银行的获利以及被抓的概率，求最大能偷多少钱。
这是一道01背包的问题，但是不太一样的是如果我们直接以概率为背包容量的话会出现一个很尴尬的问题就是实数并不可以当做数组的下标，然后我想到了对概率乘上一个较大的数（1e6之类的）然后进行背包的dp，但是这样会WA，由此可见这道题的精度还是很高的，所以这种方法我们行不通。就得换个方向
这里可以以偷到的美金的数量为背包容量进行01背包，然后求出获得(1~n)内每个美金数量所对应的不被抓住的概率。
背包容量就是可以偷到的美金的最大值——所有都偷到。
dp[i]表示的就是偷了i美金之后不被抓的概率
有一点还需要注意的就是dp[0]必须初始化为1，不然后面算出来的dp都是0了。可为什么初始化的是1呢，因为我们现在用的dp数组表示的是偷了i美金之后不被抓的概率，i等于0的意思就是一点美金都没偷，不被抓的概率当然就是1(100%)了。
为什么我们要求的是不被抓住的概率呢？
因为如果是被抓住的概率的话，算总的概率并不好求，可以自己想一下。如果第一次被抓住的概率是0.5，第二次被抓住的概率也是0.5··~第n次被抓住的概率也是0.5，那么总共被抓住的几率并不好求，因为如果第一次被抓住了，后面的就都不用考虑了，以此类推易想到不好求。
但是如果是不被抓住的概率，我们直接累乘就行了。
最后我们求出对应的每个美金的数量对应的不被抓住的概率，直接O(n)查找到概率大于等于1-p(允许被抓的最大概率)的美金数量输出即可。
具体可以看一下代码在感受一下，涉及到01背包的直接套板子就行(对和我一样不太理解背包的小伙伴适用
Code:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int m[maxn];double dp[100005],p[maxn];
int main()
{
ios::sync_with_stdio(0);
int t;
cin>>t;
while(t--)
{
memset(dp,0,sizeof(dp));
double pp;int n,sum=0;
cin>>pp>>n;
for(int i=0;i<n;i++)
{
cin>>m[i]>>p[i];
sum+=m[i];
p[i]=1-p[i];
}
dp[0]=1;//这个初始化很重要
for(int i=0;i<n;i++)
{
for(int j=sum;j>=m[i];j--)
{
dp[j]=max(dp[j],dp[j-m[i]]*p[i]);
}
}
for(int i=sum;i>=0;i--)
{
if(dp[i]>=1-pp)
{
cout<<i<<endl;
break;
}
}
}
return 0;
}Coin Change
Description:
PDF题面:戳我戳我
Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make
changes with these coins for a given amount of money.
For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent
coin, two 5-cent coins and one 1-cent coin, one 5-cent coin and six 1-cent coins, or eleven 1-cent coins.
So there are four ways of making changes for 11 cents with the above coins. Note that we count that
there is one way of making change for zero cent.
Write a program to find the total number of different ways of making changes for any amount of
money in cents. Your program should be able to handle up to 7489 cents.
Input
The input file contains any number of lines, each one consisting of a number for the amount of money
in cents.
Output
For each input line, output a line containing the number of different ways of making changes with the
above 5 types of coins.
Sample Input
11
26
Sample Output
4
13
Problem solving:
这道题的意思就是给你5种硬币，币值都给你了，在给你一个数问有几种方法可以拼出来这个数。
这是一道完全背包的题，直接套板子就行了。
这里我第一次不知道为啥TLE了，所以加上了一个记忆化搜索，也可能是cin/cout得锅。
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans[7500];
ll solve(ll x)
{
if(ans[x]) return ans[x];
int coins[13] = { 1, 5, 10, 25, 50};
ll dp[100005] = { 0 };
dp[0] = 1;
for (int i = 0; i < 6; i++)
{
for (int j = coins[i]; j <= x; j++)
{
dp[j] = dp[j] + dp[j - coins[i]];
}
}
return ans[x]=dp[x];
}
int main()
{
ll t, a;
ios::sync_with_stdio(0);
cin.tie(0);
while (cin >> a)
{
cout << solve(a)/2 << endl;
}
}悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
Description:
急！灾区的食物依然短缺！
为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。
请问：你用有限的资金最多能采购多少公斤粮食呢？
后记：
人生是一个充满了变数的生命过程，天灾、人祸、病痛是我们生命历程中不可预知的威胁。
月有阴晴圆缺，人有旦夕祸福，未来对于我们而言是一个未知数。那么，我们要做的就应该是珍惜现在，感恩生活——
感谢父母，他们给予我们生命，抚养我们成人；
感谢老师，他们授给我们知识，教我们做人
感谢朋友，他们让我们感受到世界的温暖；
感谢对手，他们令我们不断进取、努力。
同样，我们也要感谢痛苦与艰辛带给我们的财富～
Input
输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
Output
对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。
Sample Input
1
8 2
2 100 4
4 100 2
Sample Output
400
Problem solving:
这道题的意思就是给了你最大得经费，还给了你每包米的体积以及价格和这种米的个数，问你在最优的情况下可以买到的米的体积
这是一道多重背包的题，直接套板子即可。
Code:
#include<bits/stdc++.h>
using namespace std;
const int tx=1e3;
int m[tx],p[tx],h[tx],c[tx];
int main()
{
int t,n,x;
cin>>t;
while(t--)
{
cin>>n>>x;
memset(m,0,sizeof(m));
for(int i=0;i<x;i++) cin>>p[i]>>h[i]>>c[i];
for(int i=0;i<x;i++)
{
int mid=c[i];
for(int k=1;mid>0;k*=2)
{
int miid=min(k,mid);
for(int j=n;j>=p[i]*miid;j--)
{
m[j]=max(m[j],m[j-p[i]*miid]+h[i]*miid);
}
mid-=miid;
}
}
cout<<m[n]<<endl;
}
return 0;
}注意，这个背包问题中如果涉及到多组输入，dp数组的初始化是很重要的。
这些dp啊，背包的好多问题一看都感觉好像用贪心可以写，但是过一会你就会发现贪心并不能解决这些问题，还是老老实实学dp吧、、、
