链接：http://poj.org/problem?id=3900
题意：T个case，N种钻石，最大载重为M，第K种钻石具有价值ck, 重量wk， 数量为K个，要求选出最大价值
题目给出的数据范围
1 ≤ T ≤ 74,
1 ≤ N ≤ 15,
1 ≤ M ≤ 1000000000 (109),
1 ≤ Wk, Ck ≤ 1000000000 (109).
动态规划开不下那么大数组，N的个数不大，采用深搜，重要的是剪枝
首先按照性价比排一下序
然后如果当前搜到的结果res加上剩下所有钻石的价值都没有result大就剪枝
还有一个就是，因为是按照性价比排序所以如果当前结果res+剩余容量全部都用来放置这种性价比的钻石得到的价值都没有result大就剪枝
然后就是搜索顺序，按钻石数量由多到少搜索，要不然是会TLE的
最后那个价值和重量要用long long型的WA了一次，还是太弱了。
代码：
#include<cstdio> #include<algorithm> using namespace std; #define MAXN 20 #define ll long long struct Diamond{ ll val; int num; ll w; double vw; }; Diamond dia[MAXN]; ll result; ll sum[MAXN]; bool cmp(const Diamond& a, const Diamond& b) { return a.vw < b.vw; } void dfs(ll left, ll res, int cnt) { if(res > result) { result = res; } if(cnt <= 0) { return; } if(res + sum[cnt] <= result) { return; } if(res + left*dia[cnt].vw <= result) { return; } ll temp; for(int i = 0; i <= dia[cnt].num; ++ i) { temp = left - i*dia[cnt].w; if(temp < 0) { break; } dfs(temp, res + i*dia[cnt].val, cnt - 1); } } int main() { freopen("poj3900.txt", "r", stdin); int T, N; ll M; scanf("%d", &T); while(T--) { scanf("%d%lld", &N, &M); for(int i = 1; i <= N; ++ i) { scanf("%lld", &dia[i].w); dia[i].num = i; } for(int i = 1; i <= N; ++ i) { scanf("%lld", &dia[i].val); dia[i].vw = (double)dia[i].val/(double)dia[i].w; } sort(dia + 1, dia + N + 1, cmp); result = 0; sum[0] = 0; for(int i = 1; i <= N; ++ i) { sum[i] = sum[i - 1] + dia[i].num*dia[i].val; } dfs(M, 0, N); printf("%lld\n", result); } return 0; } |