1

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

 2 years ago
source link: https://forrestsu.github.io/posts/algorithm/%E8%83%8C%E5%8C%85%E4%B9%9D%E8%AE%B201-%E5%85%B3%E4%BA%8E%E5%B8%B8%E6%95%B0%E7%9A%84%E4%BC%98%E5%8C%96/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

2016年8月28日
| 字数 1903
| 阅读 40

Preface

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

关于一个常数优化的问题

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

 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个物品时只需要循环到：

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

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

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

最后： 基于上面两步优化，我在网上找个题目(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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK