关于物品大小较小的01背包
设题目给出的物品大小为(w_i)，个数为(n),总和为(N)
前言
这个东西可能纯粹是乱搞
发现WC2020 选课这个题直接被一个错误的写法爆水
ps:这个题是大小范围1~3，实际上正解复杂度很高
(w_iin{1,2})
这个范围的01背包，实际上可以
1.回撤贪心，从小到大考虑，每次要让总和加一，则决策就是 选一个1 或者 选一个2，删掉一个1
2.奇怪的dp? (先放着下面讲)
(w_iin{1,2,3})
好像是并没有很好的写法的，在WC2020选课 这道题中，由于求出的背包只需要访问最后(L)个结果
配合上面的贪心，先求出(w_iin{1,2})的，然后和3的暴力合并求出(L)个位置的结果，复杂度为(O(NL))
[
]
作为乱搞选手，然后想要提一下这个奇怪的dp
大概可以表达为
1.对于每种权值的物品分别排序
2.每个dp位置记录答案的同时，记录方案在每种权值里选择了几个
3.转移就是考虑每种权值选择剩下的最优的一个
实际上，这个dp在(w_ileq 2)时正确性显然，实际原理是与贪心一致的
而当(w_ileq 3)时，由于转移不完全，在实际随机数据测试中发现
(ps:由于比较难搞暴力，所以只有测试(nleq 1000)的)
1.可能存在一个位置的dp值没有被转移到
2.可能存在若干个位置(约0~1/60的比率，大部分情况都在1/200以下)的dp值错误
3.这个错误率在权值值域越小时错误率越低，在值域为10时几乎不会错(雾)
[
]
这似乎可以解释为什么WC出题人没有卡掉这个错误的dp，因为真的比较难卡？
[
]
然后尝试了几种乱搞性质的优化，发现
1.每次多枚举几个物品
效果不佳
[
]
2.记录前(k)大不同的dp值(实际上，是指通过比较决策是否相同来判断dp值是否相同)
当(w_ileq 3)时，(k)达到3后几乎不可能错(近万组没锅)
当(w_ileq 4)时，(k)达到6后几乎不可能错 (实际还是出现过错误，要想完全正确比较难，但是如果调整到(k=11)时上千组可能才会有一个位置不一样)
测试了(w_ileq 7)左右的情况
发现想要完全正确很难，但是调整(k)的大小后，总是可以让正确率非常高(然而这个(k)可能比较大，甚至需要记录几十个)
并且发现出现错误的位置几乎只有没有被dp到的那一个位置
[
]
3.正反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)看起来问题不大
附一下评测的代码，希望这个问题能够得到神仙的完美解决!
数据生成器
#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
",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,m);
rep(i,1,n) printf("%d %d
",A[i],B[i]);
puts("");
}
}
优化2:
#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
",c,sum);
//rep(i,0,m) if(dp[i]>=0) {
//if(s[i]!=dp[i])
//cerr<<"#"<<i<<' '<<s[i]<<' '<<dp[i]<<endl;
//}
}
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;
}
}
}
}
//ans^=s[i];
//cout<<"#"<<i<<' '<<s[i]<<' '<<dp[i][1]<<' '<<dp[i][2]<<' '<<dp[i][3]<<endl;
}
//rep(i,0,m) if(~dp[i][0].s && ~dp[i][1].s) cerr<<"#"<<i<<' '<<(dp[i][0]!=dp[i][1])<<endl;
//puts("");
Part2();
//printf("%d
",ans);
}
}
优化3:
#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 dp[N*10][12],s[N*10];
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) {
//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;
}
}
}
}
//ans^=s[i];
//cout<<"#"<<i<<' '<<s[i]<<' '<<dp[i][1]<<' '<<dp[i][2]<<' '<<dp[i][3]<<endl;
}
}
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);
//rep(i,0,m) cout<<dp[i][0].s<<' '; puts("");
}
}
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
",c,sum);
//rep(i,0,m) if(dp[i]>=0) {
//if(s[i]!=dp[i])
//cerr<<"#"<<i<<' '<<s[i]<<' '<<dp[i]<<endl;
//}
}
int main(){
//freopen("test.in","r",stdin);
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];
}
//int ans=0;
//rep(i,0,m) if(~dp[i][0].s && ~dp[i][1].s) cerr<<"#"<<i<<' '<<(dp[i][0]!=dp[i][1])<<endl;
//puts("");
Work(),Formin::Work();
Part2();
//printf("%d
",ans);
}
}