C++ 算法篇 动态规划----背包之一 01背包_01背包c++

一、01背包

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

1、基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

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

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

2、应用举例

有3个物品，背包容量为10，如下：求背包最多能放下多大价值的物品。

输入：

10 3 
3 4
4 5
5 6

输出：

11

 二维解法：

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

 初始时：我们初始化f[]全部为0

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

  f[10] = max{f[10], f[10-3]+p[1]} = max{f[10], f[7]+4} = max{0, 0+4} = 4;

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

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

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

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

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

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

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

  f[2] = f[1] = f[0] = 0;

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

  表中横轴的蓝色区域，表示当容量为v时，对第1个商品做出选择时所依赖的上一层的状态，如当v=10时，所依赖的就是f[0][10]和f[0][7]两个状态。所以当计算f[1][v]（v = 10....3）时，f[v]和[v-3]保存的就是f[0][v]和f[0][v-3]。

  第2次循环，即i = 2时，我们对物品2做出选择：

  f[10] = max{f[10], f[10-4]+p[2]} = max{f[10], f[6]+p[2]} = max{4, 4+5} = 9

  f[9] = max{f[9], f[9-4]+p[2]} = max{f[9], f[5]+p[2]} = max{4, 4+5} = 9

  f[8] = max{f[8], f[8-4]+p[2]} = max{f[8], f[4]+p[2]} = max{4, 4+5} = 9

  f[7] = max{f[7], f[7-4]+p[2]} = max{f[7], f[3]+p[2]} = max{4, 4+5} = 9

  f[6] = max{f[6], f[6-4]+p[2]} = max{f[6], f[2]+p[2]} = max{4, 0+5} = 5

  f[5] = max{f[5], f[5-4]+p[2]} = max{f[5], f[1]+p[2]} = max{4, 0+5} = 5

  f[4] = max{f[4], f[4-4]+p[2]} = max{f[4], f[0]+p[2]} = max{4, 0+5} = 5

  f[3] = 4

  f[2] = f[1] = f[0] = 0;

  第3次循环，即当i = 3时

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

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

  f[8] = max{f[8], f[8-5]+p[3]} = max{f[8], f[3]+3} = max{9, 4+6} = 10

  f[7] = max{f[7], f[7-5]+p[3]} = max{f[7], f[2]+3} = max{9, 0+6} = 9

  f[6] = max{f[6], f[6-5]+p[3]} = max{f[6], f[1]+3} = max{5, 0+6} = 6

  f[5] = max{f[5], f[5-5]+p[3]} = max{f[5], f[0]+3} = max{5, 0+6} = 6

  f[4] = 5

  f[3] = 4

  f[2] = f[1] = f[0]

  对于应表：

   如果还是疑问为什么v从小到大的顺序不可以（即内循环为：for(int v = w[i]; v <= V; ++v)），我们依旧可以按着代码，试着画一下表，一次，就很清楚了，比如同样的问题，正着走一次为：

  当i=1时：

  f[0] = f[1] = f[2] = 0

  f[3] = max{f[3], f[3-3]+p[1]} = max{0, 0+4} = 4

  f[4] = max{f[4], f[4-3]+p[1]} = max{0, 0+4} = 4

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

  以上结果貌似是对的，但是意思已经完全不是我们当初设计代码时的思想了，注意下面：

  f[6] = max{f[6], f[6-3]+p[1]} = max{0. 4+4} = 8//此时我们用的f[6]和f[3]相当于是f[1][6]和f[1][3]，而不是f[0][6]和f[0][3]！

  f[7] = max{f[7], f[7-3]+p[1]} = max{0, 4+4} = 8

  f[8] = max{f[8], f[8-3]+p[1]} = max{0, 4+4} = 8

  f[9] = max{f[9], f[9-3]+p[1]} = max{0, 8+4} = 12

  f[10] = max{f[10], f[10-3]+p[1]} = max{0, 8+4} = 12

  到此，我们清楚了为什么正向循环为何不可，因为此时f[v]保存的相当于是f[i][v]和f[i][v-w[i]]，这已经违背了我们意图！

一维解法：

综上的步骤我们可以很清楚的知道v从大到小循环可以满足题意，从表中我们也可以知道，我们如用f[i][v]存储最优结果，有很多没用的求解结果也被保存下来，从而浪费了大量的空间。如果我们用f[v]，那么保存的就是最终结果，且很好地利用了空间。

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

3、背包问题最优解回溯

通过上面的方法可以求出背包问题的最优解，但还不知道这个最优解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表的原理可以有如下的寻解方式：

• f (i,j)=f (i-1,j)时，说明没有选择第i 个商品，则回到f (i-1,j)；
• f (i,j)=f (i-1,j-w(i))+v(i)时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；
• 一直遍历到i＝0结束为止，所有解的组成都会找到。

就拿上面的例子来说吧：

• 最优解为f (3,10)=11，而f (3,10)!=f (2,10)却有 f (3,10)=f (2,10-w(3))+p(3)=f (2,5)+6=5+6=11，所以第3件商品被选中。
• 回到f (2,10-w(3))=f (2,5)；
• 而f (2,5)!=f (1,5)却有 f (2,5)=f (1,5-w(2))+p(2)=f (1,1)+5=0+5=5，所以第2件商品被选中。
• 回到f (1,5-w(2))=f (1,1)；
• V(1,1)=V(0,1)=0，所以第1件商品没被选择。

#include<bits/stdc++.h>
using namespace std;
int f[50][220]={0},w[40],p[40],a[100];
int main()
{  int i,v,V,n;
   cin>>V>>n;
   for(i=1;i<=n;i++)
      cin>>w[i]>>p[i];
   for(i=1;i<=n;i++)
   { for(v=V;v>=1;v--)
       if(v<w[i]) f[i][v]=f[i-1][v];
	   else f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+p[i]);	    
   }  
   for(i=1;i<=n;i++)   
   {  for(v=1;v<=V;v++) 
	    cout<<setw(5)<<f[i][v]; 
	  cout<<endl;
   }     
   for(i=n,v=V;i>=1;i--)
      if(f[i][v]!=f[i-1][v]) {a[i]=1;v=v-w[i];}
    for(i=1;i<=n;i++) 
	  cout<<a[i]<<" "; 	  
}

4、初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。

为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。

5、小结

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想。另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及空间复杂度怎样被优化。

5、01背包练习：

1、P2871 [USACO07DEC]手链Charm Bracelet

题目描述
有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
输入格式

第一行：物品个数N和背包大小M

第二行至第N+1行：第i个物品的重量C[i]和价值W[i]

输出格式

输出一行最大价值。

输入输出样例
输入 

4 6
1 4
2 6
3 12
2 7

输出 
23

2、P1048 采药  NOIP2005普及组第三题

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

输入格式
第一行有2个整数T(1≤T≤1000)和M(1≤M≤100)，用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式
1个整数，表示在规定的时间内可以采到的草药的最大总价值。

输入输出样例
输入

70 3
71 100
69 1
1  2

输出 
3
说明/提示
对于30%的数据，M≤10；对于全部的数据，M≤100

3、P1060 开心的金明    NOIP 2006 普及组 第二题

题目描述：

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1−5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[​j]，重要度为w[​j]，共选中了k件物品，编号依次为j1​,j2​,…,jk​，则所求的总和为：

v[​j1​]×w[​j1​]+v[​j2​]×w[​j2​]+…+v[​jk​]×w[​jk​]。

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行，为2个正整数，用一个空格隔开：N  m（其中N(<30000)表示总钱数，m(<25)为希望购买物品的个数。）

从第2行到第m+1行，第j行给出了编号为j−1的物品的基本数据，每行有2个非负整数   v   p（其中v表示该物品的价格(v≤10000)，p表示该物品的重要度(1−5)

输出格式

1个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。

输入输出样例

输入 

1000 5
800 2
400 5
300 5
400 3
200 2

输出 

3900

4、最大约数和

题目描述
选取  和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

输入格式
输入一个正整数S。

输出格式
输出最大的约数之和。

输入输出样例
输入 
11
输出 
9
说明/提示
样例说明：取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。
数据规模：S<=1000
 

5、 精卫填海

【问题描述】

发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西山之木石，以堙于东海。——《山海经》

精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？

事实上，东海未填平的区域还需要至少体积为v的木石才可以填平，而西山上的木石还剩下n块，每块的体积和把它衔到东海需要的体力分别为k和m。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为c。

输入格式

输入文件的第一行是三个整数：v、n、c。

从第二行到第n+1行分别为每块木石的体积和把它衔到东海需要的体力。

输出格式

输出文件只有一行，如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出’Impossible’（不带引号）。

输入输出样例

输入 

100 2 10
50 5
50 5

输出 

0

输入

10 2 1
50 5
10 2

输出

Impossible

说明/提示

【数据范围】

对于20%的数据，0<n<=50。

对于50%的数据，0<n<=1000。

对于100%的数据，0<n<=10000，所有读入的数均属于[0,10000]，最后结果<=c。

6、P1507 NASA的食物计划

题目背景

NASA(美国航空航天局)因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋,因此在各方压力下终止了航天飞机的历史,但是此类事情会不会在以后发生，谁也无法保证,在遇到这类航天问题时,解决方法也许只能让航天员出仓维修,但是多次的维修会消耗航天员大量的能量,因此NASA便想设计一种食品方案,让体积和承重有限的条件下多装载一些高卡路里的食物.

题目描述

航天飞机的体积有限,当然如果载过重的物品,燃料会浪费很多钱,每件食品都有各自的体积、质量以及所含卡路里,在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次.

输入格式

第一行 两个数 体积最大值(<400)和质量最大值(<400)

第二行 一个数 食品总数N(<50).

第三行－第3+N行

每行三个数 体积(<400) 质量(<400) 所含卡路里(<500)

输出格式

一个数 所能达到的最大卡路里(int范围内)

输入输出样例

输入 

320 350
4
160 40 120
80 110 240
220 70 310
40 400 220

输出 

550

7、P1164 小A点菜

题目背景

uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。

uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。

题目描述

不过uim由于买了一些辅（e）辅（ro）书，口袋里只剩M元(M≤10000)。

餐馆虽低端，但是菜品种类不少，有N种(N≤100)，第i种卖ai​元(ai​≤1000)。由于是很低端的餐馆，所以每种菜只有一份。

小A奉行“不把钱吃光不罢休”，所以他点单一定刚好吧uim身上所有钱花完。他想知道有多少种点菜方法。

由于小A肚子太饿，所以最多只能等待11秒。

输入格式

第一行是两个数字，表示N和M。

第二行起N个正数ai​（可以有相同的数字，每个数字均在1000以内）。

输出格式

一个正整数，表示点菜方案数，保证答案的范围在int之内。

输入输出样例

输入 

4 4
1 1 2 2

输出 

3

8、P1926 小书童——刷题大军

题目背景

数学是火，点亮物理的灯；物理是灯，照亮化学的路；化学是路，通向生物的坑；生物是坑，埋葬学理的人。 文言是火，点亮历史宫灯；历史是灯，照亮社会之路；社会是路，通向哲学大坑；哲学是坑，埋葬文科生。——小A

题目描述

小A“刷题”十分猖狂，明目张胆地“刷题”。他现在在小书童里发现了n样他喜欢的“题目”，每“题”都有他的需要时间，而老师布置了m项作业，每项作业都有它的需要时间及分值，老师规定k分以上算及格。小A只剩r个单位时间，他想在及格的基础上更多地“刷题”。

输入格式

第一行：n m k r。第二行：n个数，代表每“题”他的需要时间。第三行：m个数。表示每项作业它的需要时间。第四行：m个数。代表每项作业它的分值。

输出格式

一个数，代表小A能刷几道题

输入输出样例

输入 

3 4 20 100
15 20 50
10 15 40 40
5 5 10 15

输出

2

说明/提示

没有不能及格的情况，对于100%的数据，n≤10,m≤10,k≤50,r≤150

9、P1049 装箱问题  NOIp2001普及组 第4题

题目描述：

有一个箱子容量为V（正整数，0≤V≤20000），同时有n个物品（0<n≤30），每个物品有一个体积（正整数）。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式

1个整数，表示箱子容量

1个整数，表示有n个物品

接下来n行，分别表示这n个物品的各自体积

输出格式

1个整数，表示箱子剩余空间。

输入输出样例

输入 

24
6
8
3
12
7
9
7

输出 

0