01背包问题的动态规划解法递归方程为：
|
1 2 |
当 j >= wi 时, m(i, j) = max { m(i-1, j), m(i-1, j-wi) + vi }; 当 j < wi 时， m(i, j) = m(i-1, j) |
此时时间复杂度为O(n)。
使用回溯法解决01背包问题时，若可选物品为n个，则其解空间由长度为n的0-1向量组成。
此时时间复杂度为O(n2^n)。
使用分支限界法时，首先要对数据进行预处理，将物品重量价值按从小到大排列。分治限界法的缺点是占用内存大，效率不高。
时间复杂度为O(2^n)。
韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。
输入格式：
输入第一行给出两个正整数：N（<=104）是硬币的总个数，M（<=102）是韩梅梅要付的款额。第二行给出N枚硬币的正整数面值。数字间以空格分隔。
输出格式：
在一行中输出硬币的面值 V1 <= V2 <= … <= Vk，满足条件 V1 + V2 + … + Vk = M。数字间以1个空格分隔，行首尾不得有多余空格。若解不唯一，则输出最小序列。若无解，则输出“No Solution”。
注：我们说序列{A[1], A[2], …}比{B[1], B[2], …}“小”，是指存在 k >= 1 使得 A[i]=B[i] 对所有 i < k 成立，并且 A[k] < B[k]。
输入样例1：
8 9
5 9 8 7 2 3 4 1
输出样例1：
1 3 5
输入样例2：
4 8
7 2 4 3
输出样例2：
No Solution
分析：01背包问题，因为要输出从小到大的排列，可以先把硬币面额从大到小排列，然后用bool类型的choice[i][j]数组dp[i][j]是否选取，如果选取了就令choice为true；然后进行01背包问题求解，如果最后求解的结果不是恰好等于所需要的价值的，就输出No Soultion，否则从choice[i][j]判断选取的情况，i从n到1表示从后往前看第i个物品的选取情况，j从m到0表示从容量m到0是否选取(j = j – w[i])，把选取情况压入arr数组中，最后输出arr数组
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <cstdio> #include <vector> #include <algorithm> using namespace std; int dp[10010]; int w[10010]; bool choice[10010][10010]; int cmp1(int a, int b){return a > b;} int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &w[i]); sort(w + 1, w + n + 1, cmp1); for(int i = 1; i <= n; i++) { for(int j = m; j >= w[i]; j--) { if(dp[j] <= dp[j-w[i]] + w[i]) { choice[i][j] = true; dp[j] = dp[j-w[i]] + w[i]; } } } if(dp[m] != m) printf("No Solution"); else { vector<int> arr; int v = m, index = n; while(v > 0) { if(choice[index][v] == true) { arr.push_back(w[index]); v -= w[index]; } index--; } for(int i = 0; i < arr.size(); i++) { if(i != 0) printf(" "); printf("%d", arr[i]); } } return 0; } |
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个硬币买价值为m的东西，输出使用方案，使得正好几个硬币加起来价值为m。从小到大排列，输出最小的那个排列方案
分析：01背包问题，因为要输出从小到大的排列，可以先把硬币面额从大到小排列，然后用bool类型的choice[i][j]数组dp[i][j]是否选取，如果选取了就令choice为true；然后进行01背包问题求解，如果最后求解的结果不是恰好等于所需要的价值的，就输出No Soultion，否则从choice[i][j]判断选取的情况，i从n到1表示从后往前看第i个物品的选取情况，j从m到0表示从容量m到0是否选取(j = j – w[i])，把选取情况压入arr数组中，最后输出arr数组
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; int dp[10010], w[10010]; bool choice[10010][110]; int cmp1(int a, int b){return a > b;} int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &w[i]); sort(w + 1, w + n + 1, cmp1); for(int i = 1; i <= n; i++) { for(int j = m; j >= w[i]; j--) { if(dp[j] <= dp[j-w[i]] + w[i]) { choice[i][j] = true; dp[j] = dp[j-w[i]] + w[i]; } } } if(dp[m] != m) printf("No Solution"); else { vector<int> arr; int v = m, index = n; while(v > 0) { if(choice[index][v] == true) { arr.push_back(w[index]); v -= w[index]; } index--; } for(int i = 0; i < arr.size(); i++) { if(i != 0) printf(" "); printf("%d", arr[i]); } } return 0; } |
问题描述
给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
输入格式
输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。
以后N行每行两个数Wi和Vi,表示物品的重量和价值
输出格式
输出1行，包含一个整数，表示最大价值。
样例输入
3 5
2 3
3 5
4 7
样例输出
8
数据规模和约定
1<=N<=200,M<=5000.
分析：dp[i][j]表示前i件物品选择部分装入体积为j的背包后，背包当前的最大价值，
一共有n件物品，那么dp[n][m]就是前n件物品选择部分装入容量为m的背包后，背包内物品的最大价值
1.当当前输入的物品体积大于背包容量，则不装入背包，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于背包容量，考虑装或者不装两种状态，取体积最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> using namespace std; int dp[201][5001]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) { int w, v; cin >> w >> v; for(int j = 1; j <= m; j++) { if (j >= w) dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v); else dp[i][j] = dp[i-1][j]; } } cout << dp[n][m]; return 0; } |
问题描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有两个整数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。
分析：01背包问题。对于每一个输入都有采和不采两种状态。
dp[i][j]表示对于前i个草药选择部分采且总时间不超过j小时后，草药的价值的最大值
可得dp[M][T]即是所求的解。
1.当当前输入的草药所需时间大于允许的最大时间j小时的时候，则不采，dp[i][j] = dp[i-1][j];
2.当当前输入的草药所需时间小于等于允许的最大时间小时的时候，考虑采或者不采两种状态，取能够使草药总价值最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> using namespace std; int dp[101][1001]; int main() { int t, m; cin >> t >> m; for(int i = 1; i <= m; i++) { int a, b; cin >> a >> b; for(int j = 1; j <= t; j++) { if(j >= a) dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b); else dp[i][j] = dp[i-1][j]; } } cout << dp[m][t]; return 0; } |
问题描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：
“你的房间需要购买哪些物品，怎 么布置，你说了算，只要不超过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]。（其中*为乘号）
请 你帮助金明设计一个满足要求的购物单。
输入格式
输入文件 的第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
分析：01背包问题。对于每一个输入都有买和不买两种状态。
dp[i][j]表示对于前i件物品选择部分购买限定总价不超过j元后，物品的价格与重要程度乘积的总和的最大值
可得dp[m][n]即是所求的解。
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);
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> using namespace std; int dp[25][30000]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= m; i++) { int a, b; cin >> a >> b; for(int j = 1; j <= n; j++) { if(j >= a) dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + a * b); else dp[i][j] = dp[i-1][j]; } } cout << dp[m][n]; return 0; } |