背包九讲01-关于常数的优化

01背包容量为V，在求能装入物品的获得最大价值dp[V]时，有一个常数优化。（也适用于恰好装满容量为V的01背包问题）
说明:大写字母V表示背包的容量。

关于一个常数优化的问题

前提：如果我们最后只想计算出dp[V]的值，根据动归方程：

 dp[v]=max(dp[v],dp[v-ci]+wi);//i表示第i个物品

1 当计算到第n个物品时，我们只需要知道dp[V-cn]的值是多少，也就是说计算第n-1个物品的时候我们只需要计算出dp[V-cn]的值就可以停止循环了。进一步，当处理第i个物品时只需要循环到：

备注：原作者手误把公式中ｃi+1写成了ｗi。
2 在上一步的优化下，我们发现先处理花费较大的物品会使得后续物品的循环次数更少，所以我们还可以做一个优化：把物品按照花费从大到小排序。
最后：基于上面两步优化，我在网上找个题目(nyoj654)来验证下正确性,运行结果如下。

运行结果 耗时排名

代码如下：

/** nyoj: 654*/
//c header
#include <cstdlib>
#include <cstdio>
#include <cstring>
//cpp header
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;
#define M 1100000 //Max bag's Capacity
#define N 120 //Max Item's amount
#define CLS(x,v) memset(x,v,sizeof(x))
typedef pair<int,int> ppi;

/**Cap is the bag's Capacity; SumCost is the sum of Item's cost*/
int dp[M],Cap,SumCost;
/** first is cost ,second is weight*/
int cmp(ppi x,ppi y)
{
    //return true will be Swap elements
    return x.first>y.first;
}
int ZeroOnePack(int cost,int weight)
{
    SumCost-=cost;
    int bound=max(Cap-SumCost,cost);
    for(int v=Cap;v>=bound;--v)
        dp[v]=max(dp[v],dp[v-cost]+weight);
}
int solve(vector<ppi> &Items)
{
    CLS(dp,0);
    for(int i=0;i<Items.size();i++)
        ZeroOnePack(Items[i].first,Items[i].second);
    //return Answer
    return dp[Cap];
}

int main()
{
    int T,n,cost,weight;
    vector<ppi>Items;
    //large input take effect obviously
    ios::sync_with_stdio(false);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&Cap);
        SumCost=0;
        Items.clear();
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&cost,&weight);
            SumCost+=cost;
            Items.push_back(make_pair(cost,weight));
        }
        sort(Items.begin(),Items.end(),cmp);
        printf("Max experience: %d\n",solve(Items));
    }
    return 0;
}

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=654