Preface

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

关于一个常数优化的问题

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

1

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

当计算到第n个物品时，我们只需要知道dp[V-cn]的值是多少，也就是说计算第n-1个物品的时候，正常for循环下标 v 应该递减至第n-1件物品的cost，但是下一步得到答案只需要知道dp[V-cn]，我们一旦到达下标 V-cn，即可提前中止当前(n-1物品的)循环。

也就是说，当处理第i个物品时只需要循环到： formula-pack

备注：原作者手误把公式中ｃi+1写成了ｗi。

更进一步优化————物品顺序

在上一步的优化下，我们发现先处理花费较大的物品会使得后续物品的循环次数更少，所以我们还可以做一个优化：把物品按照花费从大到小排序。

最后： 基于上面两步优化，我在网上找个题目(nyoj654)来验证下正确性,运行结果如下。 run-result

cost-time-rank

代码如下：

 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
54
55
56
57
58
59
60
61
62
63
64

/** 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