头像

o_O


访客:2768

离线:17天前



o_O
2019-04-19 02:11

bug代码运行时间44ms,正常的代码运行时间369ms

有没有大神解释下这是怎么回事,是测试样例问题还是我无意中发现了一种更优算法?????

这是bug代码 在二进制优化时c>num写成了num>c;

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int dp[1010];
vector<int> v, w, t;

int main() {
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i<n; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        if (c>0) {
            int num = 1;
            while (c>0) {
                bool flag = 1;
                if (num>c) {
                    v.push_back(a*num);
                    w.push_back(b*num);
                    t.push_back(-1);
                }
                else {
                    v.push_back(a*c);
                    w.push_back(b*c);
                    t.push_back(-1);
                }
                c -= num;
                num <<= 1;
            }
        }
        else {
            v.push_back(a);
            w.push_back(b);
            t.push_back(c);
        }
    }
    for (int i = 0; i<v.size(); ++i) {
        if (t[i]<0) {
            for (int j = m; j >= v[i]; --j) {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        else {
            for (int j = v[i]; j <= m; ++j) {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
    }
    cout << dp[m] << endl;
}

这是正常代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int dp[1010];
vector<int> v, w, t;

int main() {
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i<n; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        if (c>0) {
            int num = 1;
            while (c>0) {
                if (c>num) {
                    v.push_back(a*num);
                    w.push_back(b*num);
                    t.push_back(-1);
                }
                else {
                    v.push_back(a*c);
                    w.push_back(b*c);
                    t.push_back(-1);
                }
                c -= num;
                num <<= 1;
            }
        }
        else {
            v.push_back(a);
            w.push_back(b);
            t.push_back(c);
        }
    }
    for (int i = 0; i<v.size(); ++i) {
        if (t[i]<0) {
            for (int j = m; j >= v[i]; --j) {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        else {
            for (int j = v[i]; j <= m; ++j) {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
    }
    cout << dp[m] << endl;
}



o_O
2019-04-16 08:06

题目描述

https://www.acwing.com/problem/content/description/6/

关于理解yxc大神的代码的一些笔记

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int n, m;
int f[20002], q[20002], g[20002];
int main() {
    cin >> n >> m;
    for (int i = 0; i <= n; ++i) {
        int v, w, s;
        cin >> v >> w >> s;
        memcpy(g, f, sizeof(f));
        for (int j = 0; j < v; ++j) {
            /*
            hh为队首位置
            tt为队尾位置
            数值越大,表示位置越后面
            队首在队尾后面队列为空,即hh>tt时队列为空
            */
            int hh = 0, tt = -1;
            /* 
            q[]为单调队列
            存储前个s(物品数量)中的最大值
            数组从头(hh)到尾(tt)单调递减
            */
            for (int k = j; k <= m; k += v) {

                // f[k] = g[k]; //这一行我没理解有什么用,去掉后也能ac?我认为前面使用过了memcpy,这里应该一定是相等的

                //k代表假设当前背包容量为k
                //q[hh]为队首元素(最大值的下标)
                //g[]为dp[i-1][]
                //f[]为dp[i][]

                /*
                维护一个大小为k的区间
                使最大值为前k个元素中最大
                (k - q[hh]) / v 表示拿取物品的数量(相当于最原始的多重背包dp的k)
                */
                if (hh <= tt && (k - q[hh]) / v > s) {
                    hh++;
                }

                /*
                若队内有值,该值就是前k个元素的最大值
                (k - q[hh]) / v 表示拿取物品的数量(相当于最原始的多重背包dp的k)
                q[hh]为队首元素(g[]中前k个数中最大值的下标),g[]为dp[i-1][]
                所以 g[q[hh]]为只考虑前i-1个物品时,拿前q[hh]个物品的最大价值
                */
                if (hh <= tt) {
                    f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
                }

                /*
                若队尾元素小于当前元素,则队尾元素出队;
                若队内一个元素比当前元素小,则该元素一定不会被用到(单调队列思想)
                g[q[tt]] + (k - q[tt]) / v * w 
                与
                g[k] - (k - j) / v * w
                分别表示队尾元素的值和当前元素的值
                */
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) {
                    tt--;
                }

                //去除了比当前小的元素,保证队列里的元素都比当前元素大,入队
                q[++tt] = k;
            }
        }
    }
    cout << f[m] << endl;
}

变量名换成了英文名,可能更容易理解

#include <bits/stdc++.h>
using namespace std;

int item_number, packge_volumn;
int volume, value, number;

int dp[20010];
int dp_prev[20010];
int monotone_queue[20010];

int main() {
    cin >> item_number >> packge_volumn;
    for (int i = 0; i < item_number; ++i) {
        memcpy(dp_prev, dp, sizeof(dp));
        cin >> volume >> value >> number;
        for (int j = 0; j < volume; ++j) {
            int head = 0, tail = -1;
            for (int k = j; k <= packge_volumn; k += volume) {
                if (head <= tail && (k - monotone_queue[head]) / volume > number)
                    head++;

                if (head <= tail)
                    dp[k] = max(dp[k], dp_prev[monotone_queue[head]] + (k - monotone_queue[head]) / volume * value);

                while (head <= tail && dp_prev[monotone_queue[tail]] - (monotone_queue[tail] - j) / volume * value<= dp_prev[k] - (k - j) / volume * value) {
                    --tail;
                }

                monotone_queue[++tail] = k;
            }
        }
    }
    cout << dp[packge_volumn] << endl;
}