NYOJ 654 喜欢玩warcraft的ltl (01背包常数优化)

NYOJ 654 喜欢玩warcraft的ltl (01背包常数优化)

【题目链接】：​​click here~~​​

一个常数优化

前面的伪代码中有 for v=V..1，可以将这个循环的下限进行改进。

由于只需要最后f[v]的值，倒推前一个物品，其实只要知道f[v-w[n]]即可。以此类推，对以第j个背包，其实只需要知道到f[v-sum{w[j..n]}]即可，即代码中的

for i=1..N

for v=V..0

可以改成

for i=1..n

bound=max{V-sum{w[i..n]},c[i]}

for v=V..bound

这对于V比较大时是有用的。

代码：

/** Problem: NYOJ No.654* Running time: 412MS* Complier: C++* Author: ACM_herongwei* Create Time: 9:24 2015/9/9 星期三 * zeroonebags 的常数优化*/#include #include #include #include #define CLR(c,v) (memset(c,v,sizeof(c)))using namespace std;template inline _T Max(_T a,_T b){ return (a>b)?(a):(b);}template inline _T Max(_T a,_T b,_T c){ return (a>Max(b,c))?(a):(Max(b,c));}const int COST = 1e6 + 10;const int M = 1e4 + 10;int dp[COST];int value[M];int volume[M];int main(){ int Ncase; scanf("%d",&Ncase) ; while(Ncase--){ CLR(dp,0); int max_cost, n_bags; scanf("%d%d",&n_bags, &max_cost); for (int i = 0 ; i < n_bags ; ++i){ // max:1000 scanf("%d%d",&volume[i],&value[i]); } for (int i = 0 ; i < n_bags ; ++i){ // max:1000 int sum = 0; for(int j = i ; j < n_bags ; ++j){ sum += volume[j]; } int bound = Max(max_cost-sum , volume[i]); for(int j = max_cost ; j >= bound ; j--){ // max:100 0000 if( dp[j] < dp[j-volume[i]] + value[i]){ dp[j] = dp[j-volume[i]] + value[i]; } } } printf("Max experience: %d\n",dp[max_cost]); } return 0;}/*样例输入23 107 72 33 52 53 52 1样例输出Max experience: 12Max experience: 6*/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。