## 【01背包问题】：动态规划、回溯法和分支限界法 三种算法的对比与分析（时间复杂度方面）

### 动态规划（dp）

01背包问题的动态规划解法递归方程为：

8 9
5 9 8 7 2 3 4 1

1 3 5

4 8
7 2 4 3

No Solution

## 1068. Find More Coins (30)-PAT甲级真题（01背包）

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as 104 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (<=104, the total number of coins) and M(<=102, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the face values V1 <= V2 <= … <= Vk such that V1 + V2 + … + Vk = M. All the numbers must be separated by a space, and there must be no extra space at the end of the line. If such a solution is not unique, output the smallest sequence. If there is no solution, output “No Solution” instead.

Note: sequence {A[1], A[2], …} is said to be “smaller” than sequence {B[1], B[2], …} if there exists k >= 1 such that A[i]=B[i] for all i < k, and A[k] < B[k].

Sample Input 1:
8 9
5 9 8 7 2 3 4 1
Sample Output 1:
1 3 5
Sample Input 2:
4 8
7 2 4 3
Sample Output 2:
No Solution

给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.

输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。
以后N行每行两个数Wi和Vi,表示物品的重量和价值

输出1行，包含一个整数，表示最大价值。

3 5
2 3
3 5
4 7

8

1<=N<=200,M<=5000.

1.当当前输入的物品体积大于背包容量，则不装入背包，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于背包容量，考虑装或者不装两种状态，取体积最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);

## 蓝桥杯 ALGO-30 算法训练 入学考试（01背包，动态规划）

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

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

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

70 3
71 100
69 1
1 2

3

对于30%的数据，M <= 10；
对于全部的数据，M <= 100。

dp[i][j]表示对于前i个草药选择部分采且总时间不超过j小时后，草药的价值的最大值

1.当当前输入的草药所需时间大于允许的最大时间j小时的时候，则不采，dp[i][j] = dp[i-1][j];
2.当当前输入的草药所需时间小于等于允许的最大时间小时的时候，考虑采或者不采两种状态，取能够使草药总价值最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);

## 蓝桥杯 ALGO-31 算法训练 开心的金明（01背包，动态规划）

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：
“你的房间需要购买哪些物品，怎 么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为 j1，j2，……，jk，则所求的总和为：
v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）
请 你帮助金明设计一个满足要求的购物单。

输入文件 的第1行，为两个正整数，用一个空格隔开：
N m
（其中N（<30000）表示总钱 数，m（<25）为希望购买物品的个数。）
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数
v p
（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。

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

3900

dp[i][j]表示对于前i件物品选择部分购买限定总价不超过j元后，物品的价格与重要程度乘积的总和的最大值

1.当当前输入的物品价格大于允许的最大总价j元，则不买，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于允许的最大总价j元，考虑买或者不买两种状态，取物品的价格与重要程度乘积的总和最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + t);