C++ 算法篇 动态规划----背包之二 完全背包_完全背包问题例题

完全背包

问题:有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路:

　   这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程。

像这样：f[i][v]=max{f[i-1][v-k*w[i]]+k*c[i]|0<=k*w[i]<= v}。

　    将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。

　　这个算法使用一维数组，先看伪代码：

　　for i=1..N

　　　for v=0..V

　　　　 f[v]=max{f[v],f[v-w[i]]+c[i]};

　　你会发现，这个伪代码与01背包问题的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么01背包问题中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-w[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-w[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-w[i]]，所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的道理。

　    这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：

f[i][v]=max{f[i-1][v],f[i][v-w[i]]+c[i]}，将这个方程用一维数组实现，便得到了上面的伪代码。

1、例题

【问题描述】设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。

【输入格式】

第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；

第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。

【输出格式】

仅一行，一个数，表示最大总价值。

【样例输入】

10  4
2  1
3  3
4  5
7  9

【样例输出】

max=12

#include<bits/stdc++.h>
using namespace std;
int f[220]={0},w[40],c[40];
int main()
{  int i,m,M,n;
   cin>>M>>n;
   for(i=1;i<=n;i++)
      cin>>w[i]>>c[i];
   for(i=1;i<=n;i++)
   { for(m=w[i];m<=M;m++)
      f[m]= max(f[m],f[m-w[i]]+c[i]); 
	 //for(m=1;m<=M;m++) cout<<setw(5)<<f[m]; 
	// cout<<endl; 
   }     
   cout<<f[M]; 	
}

第一次循环：

其中 f[1] = f[0] = 0，是因为重量为2的物品，根本不会影响当背包容量为1、0时的状态。所以他们依旧保持原来的状态。对应于：f[1] = f[0] = 0;第1次主循环，即当i = 1时，我们只对物品1进行选择，对于内层循环，即当v =2....10时，我们有：

f[2] = max{f[2], f[2-2]+c[1]} = max{f[2], f[0]+1} = max{0, 0+1} = 1;

f[3] = max{f[3], f[3-2]+c[1]} = max{f[3], f[1]+1} = max{0, 0+1} = 1;

f[4] = max{f[4], f[4-2]+c[1]} = max{f[4], f[2]+1} = max{0, 1+1} = 2;

f[5] = max{f[5], f[5-2]+c[1]} = max{f[5], f[3]+1} = max{0, 1+1} = 2;

f[6] = max{f[6], f[6-2]+c[1]} = max{f[6], f[4]+1} = max{0, 2+1} =3;

f[7] = max{f[7], f[7-2]+c[1]} = max{f[7], f[5]+1} = max{0, 2+1} = 3;

f[8] = max{f[8], f[8-2]+c[1]} = max{f[8], f[6]+1} = max{0, 3+1} = 4;

f[9] = max{f[9], f[9-2]+c[1]} = max{f[9], f[7]+1} = max{0, 3+1} = 4;

f[10] = max{f[10], f[10-2]+c[1]} = max{f[10], f[8]+1} = max{0, 4+1} = 5;

第二次循环：

第2次主循环，即当i = 2时，我们只对物品2进行选择，对于内层循环，即当v =3....10时，我们有：

其中 f[1] = f[0] = 0，是因为重量为3的物品，根本不会影响当背包容量为0、1、2时的状态。所以他们依旧保持原来的状态。对应于：f[1] = f[0] = 0，f[2]=1;

f[3] = max{f[3], f[3-3]+c[2]} = max{f[3], f[0]+3} = max{1, 0+3} = 3;

f[4] = max{f[4], f[4-3]+c[2]} = max{f[4], f[1]+3} = max{2, 0+3} = 3;

f[5] = max{f[5], f[5-3]+c[2]} = max{f[5], f[2]+3} = max{2, 1+3} = 4;

f[6] = max{f[6], f[6-3]+c[2]} = max{f[6], f[3]+3} = max{3, 3+3} =6;

f[7] = max{f[7], f[7-3]+c[2]} = max{f[7], f[4]+3} = max{3, 3+3} = 6;

f[8] = max{f[8], f[8-3]+c[2]} = max{f[8], f[5]+3} = max{4, 4+3} = 7;

f[9] = max{f[9], f[9-3]+c[2]} = max{f[9], f[6]+3} = max{4, 6+3} = 9;

f[10] = max{f[10], f[10-3]+c[2]} = max{f[10], f[7]+3} = max{5, 6+3} = 9;

第三次循环：

第3次主循环，即当i = 3时，我们只对物品3进行选择，对于内层循环，即当v =4....10时，我们有：

其中 f[1] = f[0] = 0，是因为重量为4的物品，根本不会影响当背包容量为0、1、2、3时的状态。所以他们依旧保持原来的状态。对应于：f[1] = f[0] = 0，f[2]=1，f[3]=3;

f[4] = max{f[4], f[4-4]+c[3]} = max{f[4], f[0]+5} = max{3, 0+5} = 5;

f[5] = max{f[5], f[5-4]+c[3]} = max{f[5], f[1]+5} = max{4, 0+5} = 5;

f[6] = max{f[6], f[6-4]+c[3]} = max{f[6], f[2]+5} = max{6, 1+5} =6;

f[7] = max{f[7], f[7-4]+c[3]} = max{f[7], f[3]+5} = max{6, 3+5} = 8;

f[8] = max{f[8], f[8-4]+c[3]} = max{f[8], f[4]+5} = max{7, 5+5} = 10;

f[9] = max{f[9], f[9-4]+c[3]} = max{f[9], f[5]+5} = max{9, 5+5} = 10;

f[10] = max{f[10], f[10-4]+c[3]} = max{f[10], f[6]+5} = max{9, 6+5} = 11;

第四次循环：

第4次主循环，即当i = 4时，我们只对物品4进行选择，对于内层循环，即当v =7....10时，我们有：

因为重量为7的物品，根本不会影响当背包容量为0、1、2、3、4、5、6时的状态。所以他们依旧保持原来的状态。对应于：f[1] = f[0] = 0，f[2]=1，f[3]=3，f[4]=5,  f[5]=5,  f[6]=6;

f[7] = max{f[7], f[7-7]+c[4]} = max{f[7], f[0]+9} = max{8, 0+9} = 9;

f[8] = max{f[8], f[8-7]+c[4]} = max{f[8], f[1]+9} = max{10, 9} = 10;

f[9] = max{f[9], f[9-7]+c[4]} = max{f[9], f[2]+9} = max{10, 1+9} = 10;

f[10] = max{f[10], f[10-7]+c[4]} = max{f[10], f[3]+9} = max{11, 3+9} = 12;

2、一个简单有效的优化

完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。

这个优化可以简单的O(N^2)地实现，一般都可以承受。另外，针对背包问题而言，比较不错的一种方法是：首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O(V+N)地完成这个优化。这个不太重要的过程就不给出伪代码了，希望你能独立思考写出伪代码或程序。

3、总结

　　完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程，分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。

4、完全背包练习：

1、P2722 [USACO3.1]总分 

题目描述：学生在我们USACO的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。
输入包括竞赛的时间,M(1 <= M <= 10,000)(不要担心,你要到了训练营中才会有长时间的比赛)和N,"种类"的数目1 <= N <= 10,000。
后面的每一行将包括两个整数来描述一个"种类":
第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。
你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分数。
来自任意的"种类"的题目数目可能任何非负数(0或更多)。
计算可能得到的最大分数

输入描述:

第 1行:M,N--竞赛的时间和题目"种类"的数目。
第 2-N+1 行:两个整数:每个"种类"题目的分数和耗时。

输出描述:

单独的一行包括那个在给定的限制里可能得到的最大的分数。

输入

300 4
100 60
250 120
120 100
35 20

输出

605

说明

{从第2个"种类"中选两题第4个"种类"中选三题}

2、郭嘉烜送礼（一）

题目描述：

郭嘉烜现在在给女朋友挑礼物，以提升女朋友对他的好感度。商店里有n种礼物，他们的库存都是无限的。第i种礼物能够提升女朋友对他的好感度v[i]，第i种礼物的价格为w[i]，现在郭嘉烜只有c元，问他应该挑选哪些礼物来使得女朋友对他的好感度提升最多。

输入描述:

第一行包括两个整数n、c。

接下来n行，每行2个数，表示第i种礼物能够提升女朋友对他的好感度v[i]与第i种礼物的价格w[i]。

输出描述:

一行。一个整数，表示最多能提升的好感度。

输入

2 2
1 1
2 1

输出

4

备注:

1<=n,c<=1000,1<=v[i],w[i]<=100

3、P1832 A+B Problem（再升级）

题目描述

1+1=? 显然是2

a+b=? 1001回看不谢

哥德巴赫猜想 似乎已呈泛滥趋势

以上纯属个人吐槽

给定一个正整数n，求将其分解成若干个素数之和的方案总数。

输入格式

一行：一个正整数n

输出格式

一行：一个整数表示方案总数

输入输出样例

输入 

7

输出 

3

说明/提示：

【样例解释】

7=7 7=2+5

7=2+2+3

【福利数据】

【输入】 20

【输出】 26

【数据范围及约定】

对于30%的数据 1<=n<=10

对于100%的数据，1<=n<=10^3

4、P1616 疯狂的采药

题目描述：

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

1. 每种草药可以无限制地疯狂采摘。

2. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 t 和代表山洞里的草药的数目 m。

第 2 到第 (m+1) 行，每行两个整数，第(i+1) 行的整数 ai​,bi​ 分别表示采摘第 i 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

输入输出样例

输入

70 3
71 100
69 1
1 2

输出

140

说明/提示

数据规模与约定

• 对于 30% 的数据，保证  m≤10^3。
• 对于 100% 的数据，保证 1≤m≤10^4，1≤t≤10^7，且  1≤m×t≤10^7，1≤ai​,bi​≤10^4。

5、P1877 [HAOI2012]音量调节

题目描述：一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。

音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件中还给定了n个整数c1,c2,c3…..cn，表示在第i首歌开始之前吉他手想要改变的音量是多少。

吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。

输入描述:

第一行依次为三个整数：n, beginLevel, maxlevel。

第二行依次为n个整数：c1,c2,c3…..cn。

输出描述:

输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于0或者高于maxLevel，输出-1。

输入

3 5 10
5 3 7

输出

10

6、P1679 神奇的四次方数

题目描述

在你的帮助下，v神终于帮同学找到了最合适的大学，接下来就要通知同学了。在班级里负责联络网的是dm同学，于是v神便找到了dm同学，可dm同学正在忙于研究一道有趣的数学题，为了请dm出山，v神只好请你帮忙解决这道题了。

题目描述：将一个整数m分解为n个四次方数的和的形式，要求n最小。例如，m=706,706=5^4+3^4,则n=2。

输入格式

一行，一个整数m。

输出格式

一行，一个整数n。

输入输出样例

输入 

706

输出

2

说明/提示

数据范围：对于30%的数据，m<=5000;对于100%的数据，m<=100,000

7、P1853 投资的最大效益

题目背景

约翰先生获得了一大笔遗产，他暂时还用不上这一笔钱，他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券，每一种债券都能在固定的投资后，提供稳定的年利息。当然，每一种债券的投资额是不同的，一般来说，投资越大，收益也越大，而且，每一年还可以根据资金总额的增加，更换收益更大的债券。

题目描述

例如：有如下两种不同的债券：①投资额4000，年利息400；②投资额3000，年利息250。初始时，有10000的总资产，可以投资两份债券①   ，一年获得800的利息；而投资一份债券①和两份债券②，一年可获得900的利息，两年后，可获得1800的利息；而所有的资产达到11800，然后将卖掉一份债券②，换购债券①，年利息可达到1050；第三年后，总资产达到12850，可以购买三份债券①，年利息可达到1200，第四年后，总资产可达到$14050。

现给定若干种债券、最初的总资产，帮助约翰先生计算，经过n年的投资，总资产的最大值。

输入格式

第一行为三个正整数s,n,d，分别表示最初的总资产、年数和债券的种类。

接下来d行，每行表示一种债券，两个正整数a,b分别表示债券的投资额和年利息。

输出格式

仅一个整数，表示n年后的最大总资产。

输入输出样例

输入

10000 4 2
4000 400
3000 250

输出 

14050

说明/提示

s≤10^6，n≤40，d≤10，a≤10^4,且a是1000的倍数，b不超过a的10%。

8、P5662 纪念品  NOIP 2019 普及组 第三题

题目描述

小伟突然获得一种超能力，他知道未来 T天 N 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。每天，小伟可以进行以下两种交易无限次：

1. 任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
2. 卖出持有的任意一个纪念品，以当日价格换回金币。

每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。T 天之后，小伟的超能力消失。因此他一定会在第 T天卖出所有纪念品换回金币。小伟现在有 M 枚金币，他想要在超能力消失后拥有尽可能多的金币。

输入格式

第一行包含三个正整数 T,N,M，相邻两数之间以一个空格分开，分别代表未来天数 T，纪念品数量 N，小伟现在拥有的金币数量 M。

接下来 T 行，每行包含 N 个正整数，相邻两数之间以一个空格分隔。第 i 行的 N 个正整数分别为 Pi,1​，Pi,2​,……,Pi,N​，其中 Pi,j​ 表示第 i天第 j种纪念品的价格。

输出格式

输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。

输入输出样例

输入 

6 1 100
50
20
25
20
25
50

输出 

305

输入 

3 3 100
10 20 15
15 17 13
15 25 16

输出 

217

说明/提示

【输入输出样例 1 说明】

最佳策略是：

第二天花光所有 100 枚金币买入 5 个纪念品 1；

第三天卖出 5 个纪念品 1，获得金币 125 枚；

第四天买入 6 个纪念品 1，剩余 5 枚金币；

第六天必须卖出所有纪念品换回 300 枚金币，第四天剩余 5 枚金币,共 305 枚金币。

超能力消失后，小伟最多拥有 305 枚金币。

【输入输出样例 2 说明】

最佳策略是：

第一天花光所有金币买入 10 个纪念品 1；

第二天卖出全部纪念品 1 得到 150 枚金币并买入 8 个纪念品 2 和 1 个纪念品 3，剩余 1 枚金币；

第三天必须卖出所有纪念品换回216 枚金币，第二天剩余1枚金币，共 217 枚金币。

超能力消失后，小伟最多拥有 217 枚金币。

【数据规模与约定】

对于 10% 的数据，T=1。

对于 30% 的数据，T≤4,N≤4,M≤100，所有价格 10≤Pi,j​≤100。

另有 15% 的数据，T≤100,N=1。

另有 15% 的数据，T=2,N≤100。

对于 100% 的数据，T≤100,N≤100,M≤103，所有价格 1≤Pi,j​≤104，数据保证任意时刻，小明手上的金币数不可能超过 10^4。

9、P2918 [USACO08NOV]买干草Buying Hay

约翰的干草库存已经告罄，他打算为奶牛们采购H(1 \leq H \leq 50000)H(1≤H≤50000)镑干草.

他知道N(1 \leq N\leq 100)N(1≤N≤100)个干草公司，现在用11到NN给它们编号.第ii公司卖的干草包重量 为P_i (1 \leq P_i \leq 5,000)Pi​(1≤Pi​≤5,000) 磅，需要的开销为C_i (1 \leq C_i \leq 5,000)Ci​(1≤Ci​≤5,000) 美元.每个干草公司的货源都十分充足， 可以卖出无限多的干草包.

帮助约翰找到最小的开销来满足需要，即采购到至少HH镑干草.

输入格式

* Line 1: Two space-separated integers: N and H

* Lines 2..N+1: Line i+1 contains two space-separated integers: P_i and C_i

输出格式

* Line 1: A single integer representing the minimum cost FJ needs to pay to obtain at least H pounds of hay.

输入输出样例

输入 

2 15 
3 2 
5 3 

输出 

9 

10、P2563 [AHOI2001]质数和分解

题目描述

任何大于 1 的自然数 n 都可以写成若干个大于等于 2 且小于等于 n 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如，9 的质数和表达式就有四种本质不同的形式：

9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7 。

这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。

试编程求解自然数 n 可以写成多少种本质不同的质数和表达式。

输入格式

文件中的每一行存放一个自然数 n(2 < n < 200) 。

输出格式

依次输出每一个自然数 n 的本质不同的质数和表达式的数目。

输入输出样例

输入

2
 
200

输出 

1
9845164