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 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; struct nodeType{ int w,d; nodeType(int iw,int id){ w = iw; d = id; } }; int dp[2][13000]; int main(){ int n = 0, m = 0; while (cin >> n >> m) { vector<nodeType> node; for (int i = 1; i <= n; i++) { int iw = 0,id = 0; cin >> iw >> id; node.push_back(nodeType(iw,id)); } memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { if (j-node[i-1].w >= 0) { dp[i%2][j] = max(dp[(i-1)%2][j-node[i-1].w]+node[i-1].d, dp[(i-1)%2][j]); }else{ dp[i%2][j] = dp[(i-1)%2][j]; } } } cout << dp[node.size()%2][m] << endl; } return 0; } |
裸的01背包问题,是DP的基础题型了,没有太多好说的。
简要说一下01背包问题的状态转移特点:按两个基准纪录数据,第一个基准是我们从0~a号物品中选,第二个基准是选择的物品已经有了多少重量b,这样组成了dp数组dp[a][b],这个数组存储的是当前状态的价值是多少。接下来我们开始dp,对于每一个当前状态(最多选择到第n个物品,已经占用了w重量),我们是从两种先前状态中导出的:1.最多选择到n-1个物品(就是当前物品还没有考虑呢),占用重量w-x(x是第n个物品重量),在这个状态上,我们添加上第n个物品。2.最多选择到n-1个物品,占用重量w,在这个状态上,我们什么也不做,直接把他当成当前状态。
在这两种先前状态中选择最好的那个(有时候因为某些原因,只能选择一个,那就选唯一的那个就好),保存下来决定为当前状态,再供以后使用。
这样我们只要读取dp[i][j]的值,就是“选择1~i中的物品,重量限定为j,最高价值是?”这个问题的答案。(没有用滚动数组的话)