关于物品大小较小的01背包

Posted on Edited on In

关于物品大小较小的01背包

设题目给出的物品大小为 \(w_i\)，个数为 \(n\) ,总和为 \(N\)。

前言

这个东西可能纯粹是乱搞。

发现 WC2020 选课这个题直接被一个错误的写法爆水。

ps: 这个题是大小范围 1~3 ，实际上正解复杂度很高。

\(w_i\in\{1,2\}\)

这个范围的 01背包，实际上可以：

  1. 回撤贪心，从小到大考虑，每次要让总和加一，则决策就是 选一个 1 或者 选一个 2，删掉一个 1

  2. 奇怪的dp? (先放着下面讲)

\(w_i\in\{1,2,3\}\)

好像是并没有很好的写法的，在 WC2020选课 这道题中，由于求出的背包只需要访问最后 \(L\) 个结果。

配合上面的贪心，先求出 \(w_i\in\{1,2\}\) 的，然后和 3的暴力合并求出 \(L\) 个位置的结果，复杂度为 \(O(NL)\)。


作为乱搞选手，然后想要提一下这个奇怪的dp，

大概可以表达为：

  1. 对于每种权值的物品分别排序，

  2. 每个dp位置记录答案的同时，记录方案在每种权值里选择了几个，

  3. 转移就是考虑每种权值选择剩下的最优的一个。

实际上，这个 dp 在 \(w_i\leq 2\) 时正确性显然，实际原理是与贪心一致的。

而当 \(w_i\leq 3\) 时，由于转移不完全，在实际随机数据测试中发现：

(ps:由于比较难搞暴力，所以只有测试\(n\leq 1000\)的)

  1. 可能存在一个位置的dp值没有被转移到

  2. 可能存在若干个位置(约 0~1/60 的比率，大部分情况都在 1/200 以下)的 dp值错误

3.这个错误率在权值值域越小时错误率越低，在值域为10时几乎不会错(雾)


这似乎可以解释为什么WC出题人没有卡掉这个错误的dp，因为真的比较难卡？


然后尝试了几种乱搞性质的优化，发现

  1. 每次多枚举几个物品。

效果不佳。


  1. 记录前 \(k\) 大不同的 dp 值(实际上，是指通过比较决策是否相同来判断 dp 值是否相同)。

当 \(w_i\leq 3\) 时，\(k\) 达到 3后几乎不可能错（近万组没锅）。

当 \(w_i\leq 4\) 时，\(k\) 达到6后几乎不可能错 （实际还是出现过错误，要想完全正确比较难，但是如果调整到 \(k=11\) 时上千组可能才会有一个位置不一样）。

测试了 \(w_i\leq 7\) 左右的情况。

发现想要完全正确很难，但是调整 \(k\) 的大小后，总是可以让正确率非常高(然而这个 \(k\) 可能比较大，甚至需要记录几十个)。

并且发现出现错误的位置几乎只有没有被dp到的那一个位置。


  1. 正反dp!

沿用上面的 前 k 大优化，调整参数。

正反 dp 就是再求一次不选 \(i\) 个时最小的花费。

然后两边取 max。

这个优化可以大幅提高正确率。

\(w=3,k=1\) 几乎不会错。

\(w=4,k=1\) 时上万组错一个，\(k=2\) 几乎不会错。

\(w=5,k=2\) 几乎不会错。

\(w=6,k=2\) 5000 组错一个，\(k=3\) 几乎不会错

参数调一下就可以了，不知道上界是多少，测了 \(w=10,k=10\) 看起来问题不大

附一下评测的代码，希望这个问题能够得到神仙的完美解决!

数据生成器

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
#include<bits/stdc++.h>
#include"windows.h"
using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=100000;

int A[N],B[N];


int main(){
    srand(GetTickCount());
    int T=10;
    printf("%d\n",T);
    int R=10,AR=20000000;
    while(T--) {
        int n=rand()%1000+1,m=0;
        rep(i,1,n) A[i]=rand()%R+1,B[i]=rand()%AR+1,m+=A[i];
        printf("%d %d\n",n,m);
        rep(i,1,n) printf("%d %d\n",A[i],B[i]);
        puts("");
    }
}

优化2:

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=1e3+10;

int n,m;
//int dp[N*10][12],s[N*10];
int A[12][N];
int a[N],b[N];


const int D=30;
struct Node{
    int dp[11],s;
    bool operator != (const Node __) const {
        if(rand()%5==0) rep(i,1,10) if(dp[i]!=__.dp[i]) return 1;
        return s!=__.s;
    }
    bool operator < (const Node __) const {
        return s<__.s;
    }
    void Add(int x){
        s+=A[x][dp[x]];
        dp[x]++;
    }
} dp[N*10][D];


void Part2(){
    static int dp[N*10];
    memset(dp,-63,sizeof dp),dp[0]=0;
    rep(i,1,n) drep(j,m,a[i]) if(dp[j-a[i]]>=0) cmax(dp[j],dp[j-a[i]]+b[i]);
    //rep(i,1,m) cmax(s[i],s[i-1]),cmax(dp[i],dp[i-1]);
    //rep(i,0,m) cout<<dp[i]<<' '<<s[i]<<endl;
    int sum=0,c=0;
    rep(i,1,n) sum+=a[i];

    rep(i,0,m) if(dp[i]>=0) {
        if(dp[i]!=::dp[i][0].s) {
            //assert(0);
            c++;
            cerr<<"#"<<i<<' '<<dp[i]<<' '<<::dp[i][0].s<<endl;
        }
    }
    if(c) fprintf(stderr,"## %d / %d\n",c,sum);
}

int main(){
    //freopen("test.in","r",stdin);
    rep(kase,1,rd()) {
        n=rd(),m=rd();

        rep(i,0,m) rep(j,0,D-1) dp[i][j].s=-1;
        dp[0][0].s=0;rep(i,1,10) dp[0][0].dp[i]=1;

        rep(i,0,10) A[i][0]=0;
        rep(i,1,n) {
            a[i]=rd(),b[i]=rd();
            A[a[i]][++A[a[i]][0]]=b[i];
        }
        rep(i,1,10) sort(A[i]+1,A[i]+A[i][0]+1,greater<int>());
        //int ans=0;
        rep(i,0,m) rep(j,0,D-1) if(~dp[i][j].s) {
            //if(i && s[i-1]>s[i]) {
            //s[i]=s[i-1];
            //rep(j,1,10) dp[i][j]=dp[i-1][j];
            //}
            rep(d,1,min(10,m-i)) {
                if(dp[i][j].dp[d]<=A[d][0]) {
                    Node t=dp[i][j]; t.Add(d);
                    rep(k,0,D-1) if(~t.s) {
                        if(dp[i+d][k]<t) {
                            if(!k || dp[i+d][k-1]!=t) swap(dp[i+d][k],t);
                            else break;
                        }
                    }
                }
            }
        }
        Part2();
    }
}

优化3:

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=1e3+10,INF=1e9+10;

int n,m;
int A[12][N];
int a[N],b[N];

const int D=10;

struct Node{
    int dp[11],s;
    bool operator != (const Node __) const {
        if(rand()%5==0) rep(i,1,10) if(dp[i]!=__.dp[i]) return 1;
        return s!=__.s;
    }
    bool operator < (const Node __) const {
        return s<__.s;
    }
    void Add(int x){
        s+=A[x][dp[x]];
        dp[x]++;
    }
} dp[N*10][D];
void Work(){
    rep(i,1,10) sort(A[i]+1,A[i]+A[i][0]+1,greater<int>());
    rep(i,0,m) rep(j,0,D-1) dp[i][j].s=-1;
    dp[0][0].s=0;rep(i,1,10) dp[0][0].dp[i]=1;
    rep(i,0,m) rep(j,0,D-1) if(~dp[i][j].s) {
        rep(d,1,min(10,m-i)) {
            if(dp[i][j].dp[d]<=A[d][0]) {
                Node t=dp[i][j]; t.Add(d);
                rep(k,0,D-1) if(~t.s) {
                    if(dp[i+d][k]<t) {
                        if(!k || dp[i+d][k-1]!=t) swap(dp[i+d][k],t);
                        else break;
                    }
                }
            }
        }
    }
}

namespace Formin{
    Node dp[N*10][D];
    void Work(){
        rep(i,1,10) sort(A[i]+1,A[i]+A[i][0]+1);
        rep(i,0,m) rep(j,0,D-1) dp[i][j].s=INF;
        dp[0][0].s=0;rep(i,1,10) dp[0][0].dp[i]=1;
        rep(i,0,m) rep(j,0,D-1) if(dp[i][j].s!=INF) {
            rep(d,1,min(10,m-i)) {
                if(dp[i][j].dp[d]<=A[d][0]) {
                    Node t=dp[i][j]; t.Add(d);
                    rep(k,0,D-1) if(~t.s) {
                        if(t<dp[i+d][k]) {
                            if(!k || dp[i+d][k-1]!=t) swap(dp[i+d][k],t);
                            else break;
                        }
                    }
                }
            }
        }
        int sum=0;
        rep(i,1,10) rep(j,1,A[i][0]) sum+=A[i][j];
        rep(i,0,m) cmax(::dp[i][0].s,sum-dp[m-i][0].s);
    }
}

void Part2(){
    static int dp[N*10];
    memset(dp,-63,sizeof dp),dp[0]=0;
    rep(i,1,n) drep(j,m,a[i]) if(dp[j-a[i]]>=0) cmax(dp[j],dp[j-a[i]]+b[i]);
    int sum=0,c=0;
    rep(i,1,n) sum+=a[i];

    rep(i,0,m) if(dp[i]>=0) {
        if(dp[i]!=::dp[i][0].s) {
            //assert(0);
            c++;
            cerr<<"#"<<i<<' '<<dp[i]<<' '<<::dp[i][0].s<<endl;
        }
    }
    if(c) fprintf(stderr,"## %d / %d\n",c,sum);
}

int main(){
    rep(kase,1,rd()) {
        n=rd(),m=rd();

        rep(i,0,10) A[i][0]=0;
        rep(i,1,n) {
            a[i]=rd(),b[i]=rd();
            A[a[i]][++A[a[i]][0]]=b[i];
        }
        Work(),Formin::Work();
        Part2();
    }
}