【题目链接】：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 <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#define CLR(c,v) (memset(c,v,sizeof(c)))using namespace std;template <typename _T>inline _T Max(_T a,_T b){return (a>b)?(a):(b);}template <typename _T>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:1000scanf("%d%d",&volume[i],&value[i]);}for (int i = 0 ; i < n_bags ; ++i){ // max:1000int 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 0000if( 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*/
版权声明：本文为博主原创文章，未经博主允许不得转载。
，这个社会是存在不公平的，不要抱怨，因为没有用！人总是在反省中进步的！
