锐客网

  1. 首页 > it技术 > >

背包问题（3）（完全背包）

完全背包也是一种基本的背包问题模型，其基本特点是：每种物品可以放无限多次。
【背包问题（3）（完全背包）】这个问题非常类似于0/1背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。
完全背包问题的一般描述为：有N个物品，第i个物品的重量与价值分别为W[i]与P[i]。背包容量为V，问在每个物品有无限个（物品必须保持完整）的情况下，如何让背包装入的物品具有更大的价值总和。
其一般解题思路为：
令 f[i][j] 表示从编号1~i的物品中挑选任意数量的任意物品放入容量为j的背包中得到的最大价值，那么有
f[i][j]=max { f[i?1][j]，f[i?1][j?k?W[i]]+k?P[i] }（0≤k && k?W[i]≤j）
编写代码时，可采用如下的循环。
for ( i=1; i<=N; i++)// 依次对每个物品进行处理
for (j=1; j<=V; j++)
for (k=1; k<=V/W[i]; k++)// 物品最多只能放多少件
{
If (k*W[i]<=j)
f[i][j]=max(f[i-1][j],f[i-1][j-k*W[i]]+k*P[i]);
else
f[i][j]=f[i-1][j];
}
所求的最优值为f[N][V]。
同样完全背包也可以进行空间优化，将二维数组优化为一维数组，即
f[j]=max { f[j]，f[j?k?W[i]]+k?P[i] }（0≤k && k?W[i]≤j）
编写代码时，一般采用如下的二重循环。
?for (i=1; i<=N; i++)// 装入背包的物品个数为N
for ( j=W[i]; j<=V; j++)// 完全背包按由小到大顺序枚举重量
f[j]=max(f[j],f[j-W[i]]+P[i]); // 状态转移
所求的最优值为f[V]。
由上面的二重循环可以发现，完全背包采用的二重循环与0/1背包采用的二重循环只有内循环j的循环次序不同。
在0/1背包中内循环j要按照物品重量V~W[i]的逆序来循环。这是因为要保证第i次循环中的状态f[i][j]是由状态f[i-1][j-W[i]]递推而来，从而保证每件物品只选一次。也就是要保证在考虑“选入第i件物品”时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][j-W[i]]。
而完全背包的特点恰好是每种物品可选无限件，所以在考虑“加选一件第i种物品”时，正好需要一个可能已选入第i种物品的子结果f[i][j-W[i]]，所以就可以并且必须采用W[i]~V的顺序循环。
【例1】买干草
问题描述
约翰的干草库存已经告罄，他打算为奶牛们采购 H(1≤H≤50000) 磅干草。
他知道N(1≤N≤100) 个干草公司，第i公司卖的干草包重量为Pi (1≤Pi≤5,000) 磅，需要的开销为Ci (1≤Ci≤5,000)美元。每个干草公司的货源都十分充足， 可以卖出无限多的干草包。
帮助约翰找到最小的开销来满足需要，即采购到至少H 磅干草。
输入
第1行包含两个整数N和H
第2~N+1行，每行两个整数，分别是Pi和Ci。
输出
采购到至少H 磅干草的最小开销。
输入样例
2 15
3 2
5 3
输出样例
9
（1）编程思路。
由于要采购到至少H 磅干草，因此背包的容量应设置为H+maxp，其中maxp为所有N个公司卖的干草包最大重量。
定义数组int f[55005]; ,其中f[i]表示购买i磅干草所需的最小花费，进行完全背包处理，求得各容量背包的最小花费。之后，循环在f[H]~f[H+maxp]中找到最小值即可。
（2）源程序。

#include #include int main() { int h,n; scanf("%d%d",&n,&h); int p[105],c[105]; int maxp=0; int i,j; for (i=1; i<=n; i++) { scanf("%d%d",&p[i],&c[i]); if (maxpp[i]; } int f[55005]; memset(f,0x3f,sizeof(f)); f[0]=0; for (i=1; i<=n; i++) { for (j=p[i]; jf[j-p[i]]+c[i]) f[j]=f[j-p[i]]+c[i]; } } int res=0x7fffffff; for (i=h; if[i]) res=f[i]; printf("%d\n",res); return 0; }

将上面的源程序提交给洛谷题库P2918 [USACO08NOV]Buying Hay S（https://www.luogu.com.cn/problem/P1776），测评结果为“Accepted”。
【例2】2 的次幂的和
题目描述
给出一个整数 N，将 N 分解为若干个 2 的次幂的和，共有多少种方法？
例如，当N=7时，所有合法方案如下：
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+2+2
1+1+1+4
1+2+2+2
1+2+4
输入格式
输入一个整数 N（1≤N≤106）。
输出格式
输出方案数对109 取模的结果。
输入样例
7
输出样例
6
（1）编程思路。
本题可以看成背包容量为n，而每个物品重量是2k 的求方案数的完全背包问题。
（2）源程序。
#include int f[1000001]={0}; int main() { int i=1,j,k=0; int p[25]; while (i<1000000) { p[k++]=i; i=i*2; } int n; scanf("%d",&n); f[0]=1; for (i=0; i
将上面的源程序提交给洛谷题库P6065 [USACO05JAN]Sumsets S（https://www.luogu.com.cn/problem/P6065），测评结果为“Accepted”。
【例3】债券投资
问题描述
某银行每年初售卖几种债券供客户购买投资。这几种债券有固定的面值，并提供固定数额的年利息，在每年年底支付给所有者。债券没有固定期限。债券有不同的大小，较大的通常会带来更好的收益。
假设有两种债券供投资：价值为4000元的债券，年利息为200元；价值为3000元的债券，年利息为120元。
某客户有10000元的资本，若投资1年，他可以购买两张4000元的债券，到期年利息为400元；也可以购买两张3000元的债券和一张4000元的债券，到期年利息为440元。
给定一个开始的投资金额和投资年数，以及一些债券的价值和利息，求出在给定的时间段内，该金额可能会增长到多大。注意考虑购买和出售债券的最佳时间表，即每年收益获得后，有更优的投资组合，可以卖出债券再重新购买。
输入
输入第一行包含一个正整数N，它是测试用例的数量。
每个测试用例的第一行包含两个正整数：起始金额（最多1000万元）和资本可能增长的年数（最多40年）。
下一行包含一个数字：可供投资的债券种数d（1<=d<=10）。
接下来的d行分别描述每种债券的情况，由两个正整数组成：债券的价值和该债券的年利息。债券的价值总是1000元的倍数。债券的利息永远不会超过其价值的10%。
输出
对于每个测试用例，在单独的一行上输出————是在一个最佳的买卖时间表之后，在周期结束时的资本。
（1）编程思路。
将初始的总金额看成背包的容量，每种债券的收益作为价值，面值作为物品重量，进行完全背包处理。
由于每年收益获得后，有更优的投资组合，可以卖出债券再重新购买。因此，对每年的投资组合均进行完全背包处理，而最初1年的背包容量为V，之后每年的背包容量均需要加上上一年的收益。
另外，由于债券的价值总是1000元的倍数，因此为了减少内存存储量，将金额除以1000，以减少钱的数量。
（2）源程序。
#include #include int f[5000000]; int max(int a,int b) { return a>b?a:b; } int main() { int t; scanf("%d",&t); while (t--) { memset(f,0,sizeof(f)); int v,p; scanf("%d%d",&v,&p); int n; scanf("%d",&n); int c[20],w[20]; int i,j,k; for (i=0; i
将上面的源程序提交给北大OJ题库POJ 2063 Investment（http://poj.org/problem?id=2063），测评结果为“Accepted”。
【例4】牛的叫声
题目描述
农夫约翰的N（1≤N≤100）个牧场都是沿着一条笔直的道路分布的。每一个牧场可能有许多种品种的奶牛；约翰拥有B（1≤B≤20）个不同品种的奶牛，而第i种奶牛的叫声音量为 Vi（1≤Vi≤100）。此外，有一股强风沿着道路吹来，将牛的叫声从左往右传递，如果某个牧场的总音量是x，那么它将传递x?1 的音量到右边的下一个牧场。这就意味着，一个牧场里的总音量是处在该牧场的奶牛所发出的音量加上左边前一个牧场的总音量?1 。数据保证，每一个牧场内由该牧场所有奶牛所发出的总音量最多为100000。
约翰在奶牛聚集的牧场里安装了麦克风，这样他能计算出从中听到的所有牛叫声的总音量，以便以此确定奶牛的数量。
例如，约翰拥有5个牧场，每个牧场总音量从左到右分别为为0、17、16、20、19。约翰有两种不同品种的奶牛；第一种奶牛的叫声音量是5，第二种奶牛的叫声音量是7。
由此可推知，2号牧场场有2头1号品种的奶牛，1头2号品种奶牛；这样2号牧场牛叫声的总音量为（2*5+7=17），3号牧场没有牛，前一个牧场传递来的总音量为16，4号牧场有1头1号品种的奶牛，其叫声加上传递过来的音量正好为20。这样，计算出有4头奶牛。
输入
第1行：两个用空格分隔的整数N和B。
第2…B+1行：第i+1行包含整数 Vi。
第B+2...B+N+1行：第 B+i+1行表示在第i个牧场内所能监听到的总音量。
输出
共一行，即约翰拥有的最小奶牛数量。
输入样例
5 2
5
7
0
17
16
20
19
输出样例
4
（1）编程思路。
设a[i]为第i个农场的总音量，b[i]为第i个农场的奶牛产生的音量。显然，若a[i-1]不为0，则b[i]=a[i]-(a[i-1]-1)；否则，b[i]=a[i]。
有了每个农场奶牛产生的音量b[i]后，对每个农场进行完全背包处理，用B种物品（B种奶牛，每种奶牛的叫声音量作为重量）以最少的数量去装满容量为b[i]的背包，求得每个农场的最小奶牛数量。将每个农场通过完全背包求得的最小数量累加起来就是所求的答案。
（2）源程序。
#include int min(int a,int b) { return a
将上面的源程序提交给洛谷题库P2214 [USACO14MAR]Mooo Moo S（https://www.luogu.com.cn/problem/P2214），测评结果为“Accepted”。
【例5】纪念品
问题描述
小伟突然获得一种超能力，他知道未来T天N种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。
每天，小伟可以进行以下两种交易无限次：
任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
卖出持有的任意一个纪念品，以当日价格换回金币。
每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。
T天之后，小伟的超能力消失。因此他一定会在第T天卖出所有纪念品换回金币。
小伟现在有M枚金币，他想要在超能力消失后拥有尽可能多的金币。
输入
第一行包含三个正整数 T, N, M（T≤100，N≤100，M≤1000），相邻两数之间以一个空格分开，分别代表未来天数T，纪念品数量N，小伟现在拥有的金币数量M。
接下来T行，每行包含N个正整数，相邻两数之间以一个空格分隔。第i行的N个正整数分别为Pi,1，Pi,2，…，Pi,N ，其中Pi,j（1≤Pi,j ≤10000）表示第i天第j种纪念品的价格。
输出
输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。
输入样例
3 3 100
10 20 15
15 17 13
15 25 16
输出样例
217
（1）编程思路。
T天投资，可以看成第1天买入，第2天全部卖出；第2天又卖出后又买入，第3天全部卖出；……；第T-1天卖出后又买入，第T天全部卖出。由于同一种纪念币当天买卖价格相同，因此同一种纪念币某天卖出又买进后相当当天没有进行买卖，也就是一直持有该纪念币。这样，本题可采用完全背包求解，每天投资用完全背包计算收益，共进行T-1天完全背包。
每天完全背包时，将当天手里的金币数当做背包的容量（初始时为M，之后每天结束后将当天的收益加到M上，作为下一天的背包容量），把纪念品当天的价格当成它的重量，把纪念品下一天的价格与当天的价格的差值当做它的价值。
设f[i]为用i个金币去购买纪念品所能盈利的最大值（不含成本），则有
f[j]=max(f[j],f[j?price[i][k]]+price[i][k+1]?price[i][k]); （k代表第k天）
（2）源程序。
#include #include int max(int a,int b) { return a>b?a:b; } int main() { int t,n,m; scanf("%d%d%d",&t,&n,&m); intp[101][101], f[10001]; int i,j; for (i=1; i<=t; i++) for (j=1; j<=n; j++) scanf("%d",&p[j][i]); int k; for (k=1; k
将上面的源程序提交给洛谷题库P5662 [CSP-J2019] 纪念品（https://www.luogu.com.cn/problem/P5662），测评结果为“Accepted”。
【例6】奶酪塔
问题描述
FJ要建一个奶酪塔，高度最大为T（1 <= T <= 1,000）。他有N（1 <= N <= 100）种奶酪。第i种奶酪的高度为Hi（一定是5的倍数），价值为Vi。一块高度Hi>=K的奶酪被称为大奶酪，一个奶酪如果在它上方有大奶酪（如果有多块就只算一次），它的高度Hi就会变成原来的4/5。FJ想让他的奶酪塔价值和最大。请你求出这个最大值。
输入
第一行三个数N,T,K，意义如上所述。
接下来n行，每行两个数Vi，hi。
输出
奶酪塔的最大价值
输入样例
3 53 25
100 25
20 5
40 10
输出样例
240
（1）编程思路。
如果没有大奶酪，这个题目可以用完全背包模板来做。但是加上了大奶酪，因为被大奶酪压着的奶酪高度会变成原来的4/5，所以需要把有大奶酪和没有大奶酪分开来看。
定义数组int f[1010][2]={0}; ，其中f[i][0]表示没有大奶酪时高度为i的奶酪塔的最大价值和；f[i][1]表示有大奶酪时高度为i的奶酪塔的最大价值和
如果没有大奶酪，则f[j][0]=max(f[j][0],f[j-h[i]][0]+v[i]);
如果枚举到的某个奶酪正好是大奶酪，则f[j][1]=max(f[j][1],f[(j-w[i])*4/5][0]+v[i]);
如果某个奶酪上能放大奶酪，也就是f[j-w[i]*4/5][1]存在解，则f[j][1]=max(f[j][1],f[j-w[i]*4/5][1]+v[i]);
另外，需要将奶酪按其高度先从大到小排序，这样先枚举大奶酪，再枚举小奶酪；再将全部的大奶酪按高度从小到大排列。
（2）源程序。
#include struct Node { int v,h; }; int max(int a,int b) { return a>b?a:b; } int main() { int n,T,k; scanf("%d%d%d",&n,&T,&k); struct Node a[105],temp; int i,j; int cnt=0; for (i=1; i<=n; i++) { scanf("%d%d",&a[i].v,&a[i].h); if(a[i].h>=k)cnt++; } for (i=1; ia[j+1].h) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } int f[1010][2]={0}; for (i=1; i<=T; i++) f[i][1]=-1; for (i=1; i<=n; i++) for (j=a[i].h; j<=T; j++) { f[j][0]=max(f[j][0],f[j-a[i].h][0]+a[i].v); if (f[j-a[i].h*4/5][1]!=-1) f[j][1]=max(f[j][1],f[j-a[i].h*4/5][1]+a[i].v); if (a[i].h>=k) f[j][1]=max(f[j][1],f[(j-a[i].h)*4/5][0]+a[i].v); } printf("%d\n",max(f[T][0],f[T][1])); return 0; }

将上面的源程序提交给洛谷题P2979 [USACO10JAN]Cheese Towers S（https://www.luogu.com.cn/problem/P2979），测评结果为“Accepted”。
【例7】股票市场
问题描述
尽管奶牛天生谨慎，它们仍然在住房抵押信贷市场中大受打击，现在它们准备在股市上碰碰运气。贝西有内部消息，她知道S 只股票在今后 D 天内的价格。
假设在一开始，她筹集了 M 元钱，那么她该怎样操作才能赚到最多的钱呢？贝西在每天可以买卖多只股票，也可以多次买卖同一只股票，交易单位必须是整数，数量不限。举一个牛市的例子：
假设贝西有 10 元本金，股票价格如下：
背包问题（3）（完全背包）
文章图片

最赚钱的做法是：今天买入 A 股 1 张，到明天把它卖掉并且买入 B 股 1 张，在后天卖掉 B股，这样贝西就有 24 元了。
输入
第一行：三个整数 S， D 和 M（2≤S≤50 ，2≤D≤10 ，1≤M≤200000）。
第二行到第 S + 1 行：第 i + 1 行有 D 个整数，表示第 i 种股票在第一天到最后一天的售价。
输出
单个整数：表示奶牛可以获得的最大钱数，保证这个数不会超过 500000。
输入样例
2 3 10
10 15 15
13 11 20
输出样例
24
（1）编程思路。
D天的股票投资，可以看成第1天买入，第2天全部卖出；第2天又卖出后又买入，第3天全部卖出；……；第D-1天卖出后又买入，第D天全部卖出。由于同一种股票当天的交易价格相同，因此同一种股票某天卖出又买入，相当当天没有进行交易，也就是一直持有该股票。这样，本题可采用完全背包求解，每天投资用完全背包计算收益，从第2天到第D天共进行D-1天完全背包。
每天完全背包时，将当天手里的可投资金额数当做背包的容量（初始时为M，之后每天结束后将当天的收益加到M上，作为下一天的背包容量），把股票前一天的交易价格当成它的重量（前一天买入的），把股票当天的交易价格与前一天的交易价格的差值当做它的价值。
设f[i]保存投资i元时获得的最大收益。
状态转移方程为 f[i]=max{f[i],f[i-a[j][k-1]]+a[j][k]-a[j][k-1]}
（2）源程序。
#include #include int max(int a,int b) { return a>b?a:b; } intf[500001]; int main() { int s,d,m; scanf("%d%d%d",&s,&d,&m); int a[51][11]; int i,j; for (i=1; i<=s; i++) for (j=1; j<=d; j++) scanf("%d",&a[i][j]); for (int k=2; k<=d; k++) { memset(f,0,sizeof(f)); int maxx=0; for (i=1; i<=s; i++) { for (j=a[i][k-1]; j<=m; j++) { f[j]=max(f[j],f[j-a[i][k-1]]+a[i][k]-a[i][k-1]); maxx=max(f[j],maxx); } } m+=maxx; } printf("%d\n",m); return 0; }

将上面的源程序提交给洛谷题P2938 [USACO09FEB]Stock Market G（https://www.luogu.com.cn/problem/P2938），测评结果为“Accepted”。
练习题
1．P1474 [USACO2.3]Money System（https://www.luogu.com.cn/problem/P1474）
背包问题（3）（完全背包）
文章图片
背包问题（3）（完全背包）
文章图片
#include int main() { int v,n; scanf("%d%d",&v,&n); long long f[10001]={0}; int a[26]; int i,j; for (i=0; i
View Code 2．P1616 疯狂的采药（https://www.luogu.com.cn/problem/P1616）
背包问题（3）（完全背包）
文章图片
背包问题（3）（完全背包）
文章图片
#include long long f[10000001]={0}; int main() { int t,m; scanf("%d%d",&t,&m); int a[10001],b[10001]; int i,j; for (i=1; i<=m; i++) scanf("%d%d",&a[i],&b[i]); for (i=1; i<=m; i++) for (j=a[i]; j<=t; j++) { if (f[j]
View Code 3．P1679 神奇的四次方数（https://www.luogu.com.cn/problem/P1679）
背包问题（3）（完全背包）
文章图片
背包问题（3）（完全背包）
文章图片
#include #include int main() { int p[20]={1}; int i,j; for (i=1; i<=18; i++) p[i]=i*i*i*i; int m; scanf("%d",&m); int n=(int)sqrt(sqrt(1.0*m)); int f[105001]; f[0]=0; for (i=1; i<=m; i++) f[i]=1<<30; for (i=1; i<=n; i++) for (j=p[i]; j<=m; j++) if (f[j]>f[j-p[i]]+1) f[j]=f[j-p[i]]+1; printf("%d\n",f[m]); return 0; }

View Code 4．P2722 [USACO3.1]总分 Score Inflation（https://www.luogu.com.cn/problem/P2722）
背包问题（3）（完全背包）
文章图片
背包问题（3）（完全背包）
文章图片
#include int main() { int m,n; scanf("%d%d",&m,&n); int p[10001],t[10001],f[10001]={0}; int i,j; for (i=1; i<=n; i++) scanf("%d%d",&p[i],&t[i]); for (i=1; i<=n; i++) for (j=t[i]; j<=m; j++) { if (f[j]
View Code 5．P2737 [USACO4.1]麦香牛块（https://www.luogu.com.cn/problem/P2737）
背包问题（3）（完全背包）
文章图片
背包问题（3）（完全背包）
文章图片
#include #define MAXNUM 65636 int main() { int opt[MAXNUM+5]={0}; int n; scanf("%d",&n); int i,j; opt[0]=1; for (i=1; i<=n; i++) { int v; scanf("%d",&v); for (j=v; j<=MAXNUM; j++) { if (opt[j-v]==1) opt[j]=1; } } for (i=MAXNUM; i>=1; i--) if (opt[i]==0) break; if (i>65536) printf("0\n"); elseprintf("%d\n",i); return 0; }

View Code 6．POJ1252 Euro Efficiency（http://poj.org/problem?id=1252）
背包问题（3）（完全背包）
文章图片
背包问题（3）（完全背包）
文章图片
#include #include int min(int a,int b) { return a=0; j--) f[j] = min(f[j], f[j+value[i]] + 1); int max = 0, sum = 0; for (i=1; i<=100; i++) { sum += f[i]; if (f[i] > max) max = f[i]; } printf("%.2f %d\n", sum/100.0, max); } return 0; }

View Code 7．POJ1384 Piggy-Bank （http://poj.org/problem?id=1384）
背包问题（3）（完全背包）
文章图片
背包问题（3）（完全背包）
文章图片
#include #include int min(int a,int b) { if (a
View Code 8．POJ1882 Stamps（http://poj.org/problem?id=1882）
背包问题（3）（完全背包）
文章图片
背包问题（3）（完全背包）
文章图片
#include #define INF 99999999 int min(int a,int b) { return a s) break; j--; if (j>ans) { ans = j; index = i; } else if (j== ans) { if (d[i]
View Code

    推荐阅读


    上一篇：用一个文件，实现迷你|用一个文件，实现迷你 Web 框架

    下一篇：Mybatis-Plus|Mybatis-Plus 如何实现一对多关系 举例 用户与角色