背包DP
POJ3093
题意
给定个物品和背包容量
，求将背包尽量放满的方案数。（尽量放满指的是剩余物品中重量最小的物品都不能再放入背包）
题解
考虑到背包要放的尽量满，所以额外枚举一下没有放入背包的最小物品即可。
具体实现上，可以先将重量升序排序，然后枚举第k个物品最终没有放入背包。
则第到第
的物品必然放入背包，同时对第
到第
的物品做01背包后，将满足条件的方案数统计下即可。
状态定义：表示去掉不放入背包的最小物品
后，背包装入总重量为
的方案数
目标：(
为前
个物品已放入背包后，背包的最大容量)
边界：
转移方程：
PS：本题存在如下坑点。
1 一个物品都放不进背包的情况被视为方案数为，因此需要在开始位置特判。
2 所有物品全放入背包都可以的情况被视为方案数为，同样需要特判。
3 当枚举到第个物品放入背包后，背包恰好放满的情况下，当前的答案就是
，不再进行dp。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxv=30+5;
const int maxd=1000+5;
const int INF=0x3f3f3f3f;
int T,kase=0;
int V,D;
int v[maxv];
int sum[maxv];
ll d[maxd];
ll ans;
void init(){
ans=0ll;
}
void dp(){
for(int k=1;k<=V;k++){ //枚举剩余的最小物品k
int maxD=D-sum[k-1]; //则前k-1个物品已经放入背包，背包的最大容量变为D-sum[k-1]
if(maxD<0) break;
if(maxD==0){
ans++;
continue;
}
memset(d,0,sizeof(d));
d[0]=1;
for(int i=k+1;i<=V;i++) for(int j=maxD;j>=v[i];j--) d[j]+=d[j-v[i]];
for(int i=max(0,maxD-v[k]+1);i<=maxD;i++) ans+=d[i];
/*
for(int i=max(0,maxD-v[k]+1);i<=maxD;i++){
D(k);D(maxD);D(i);D(d[i]);E;
}
*/
}
if(sum[V]<=D) ans++;
}
int main() {
ios::sync_with_stdio(false);
//freopen("POJ3093.in","r",stdin);
cin>>T;
while(T--){
cout<<++kase<<" ";
cin>>V>>D;
init();
for(int i=1;i<=V;i++) cin>>v[i];
sort(v+1,v+V+1);
if(v[1]>D){
cout<<0<<endl;
continue;
}
// reverse(v+1,v+V+1);
for(int i=1;i<=V;i++) sum[i]=sum[i-1]+v[i];
dp();
cout<<ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
BZOJ2748
题意
给你初始数的大小和所能达到最大数的大小
。
再给你个数让你每次加上这个数或减去这个数，但不能超出区间
，求最后得到的最大结果。
题解
因为每一层都有两个转移方向，同时又存在一层内没有任何一个合法的状态转移的情况。
因此，01背包时不能压缩掉第一个维度。（因为需要确定第层是否能转移到）
其他部分就是01背包的模板。
状态定义：表示处理完第i个物品，背包装入总重量为j的存在性
目标：
边界：
转移方程：
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50+5;
const int maxl=1000+5;
const int INF=0x3f3f3f3f;
int n,bl,ml,c[maxn];
int d[maxn][maxl];
void dp(){
memset(d,0,sizeof(d));
d[0][bl]=1;
for(int i=1;i<=n;i++) for(int j=0;j<=ml;j++){
if(j+c[i]<=ml) d[i][j]|=d[i-1][j+c[i]];
if(j-c[i]>=0) d[i][j]|=d[i-1][j-c[i]];
}
for(int j=ml;j>=0;j--) if(d[n][j]){
cout<<j;
return;
}
cout<<-1;
}
int main() {
ios::sync_with_stdio(false);
// freopen("2748.in","r",stdin);
cin>>n>>bl>>ml;
for(int i=1;i<=n;i++) cin>>c[i];
dp();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
BZOJ1190
题意
个物品，选取若干个，使得重量不超过
的情况下，总价值最大。
数据保证每个物品的重量符合
题解
这是一道按位划分后，从低位向高位做分层背包的题目。
首先，考虑利用题目数据的条件，即每个物品的质量都可以表示为的形式。
这意味着，如果按照的值，对所有物品进行分组后(
的物品属于第
组)，每组内所有
的值的和最大为
。
我们将组号设为dp数组的第一维(范围)，组内所有
的值设为dp数组的第二维(范围
)。
于是，dp数组的空间便可以承受。
状态定义：表示在只使用第i组内的物品，背包已经占用的重量为k的最大价值
目标：所有值，用于下一步计算
边界：
转移方程：(
循环枚举第
组内的所有物品，向量
保存第
组内的物品的
值)
接下来考虑如何用上述dp数组，将所有组合并起来计算答案。
状态定义：表示在前i组中，背包已经占用的重量为
加上
二进制第
位以下的体积的最大价值（可近似理解为对上述状态求前缀和）
目标：(len表示
的最大的len，这就意味着需要考虑所有在转移方程中考虑
几位上本来就有的
，即对应转移方程中的
和递推
前缀和数组时的向上取整)
边界：
转移方程：(
循环枚举在
组内选择的物品体积，则
为在第
组内选择的物品体积)
其他细节详见代码注释。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int maxa=10+5;
const int maxb=30+5;
const int maxm=1000+5;
const int INF=0x3f3f3f3f;
int n,W;
vector<int>G[maxb],V[maxb];
int w[maxb];
int d[maxb][maxm];
int len;
void init(){
len=0;
memset(d,0,sizeof(d));
memset(w,0,sizeof(w));
memset(G,0,sizeof(G));
memset(V,0,sizeof(V));
}
int main() {
// ios::sync_with_stdio(false);
//freopen("BZOJ1190.in","r",stdin);
while(scanf("%d%d",&n,&W)){
if(n==-1&&W==-1) break;
init();
int weight,value;
for(int i=1;i<=n;i++){
scanf("%d%d",&weight,&value);
int a,b=0;
while(!(weight&1)) weight>>=1,b++;
a=weight;
len=max(len,b);
G[b].push_back(a);
w[b]+=a;
V[b].push_back(value);
//按照b的值分组，在每一组内记录对应的a作为重量，value作为价值
}
//首先对每一组进行01背包
//d[i,k]表示在第i组内，背包已经占用的重量为k的最大价值
//这时len是组数
for(int i=0;i<=len;i++){
for(int j=0;j<G[i].size();j++){
for(int k=w[i];k>=G[i][j];k--){
d[i][k]=max(d[i][k],d[i][k-G[i][j]]+V[i][j]);
}
}
}
while(W>>len) len++;
len--;
//这时len是表示2^len<=W的最大的len
// D(len);E;
//d[i,j]表示在第0~i组中，背包已经占用的重量为$j*2^_i$加上W二进制第i位以下的体积的最大价值
for(int i=1;i<=len;i++){
w[i]+=(w[i-1]+1)/2; //w[i]=w[i]+ceil(w[i-1]/2)
for(int j=w[i];j>=0;j--){ //w[i]表示前i组背包的最大加权重量
for(int k=0;k<=j;k++){
d[i][j]=max(d[i][j],d[i][j-k]+d[i-1][min(w[i-1],k*2+((W>>i-1)&1))]); //k*2是因为进了一位
}
}
}
//按照d的状态定义，答案就是d[len,1]
printf("%d\n",d[len][1]);
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
