1.背包是小于等于的体积
1.1思路提供法
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010,mod=1e9+7;
int n,m;
int f[N][N],g[N][N];
int main(){
scanf("%d%d",&n,&m);
//因为是不少于的背包,所以一开始不少于i的初始状态都只有有一种装法,就是啥也不装
for(int i=0;i<=m;i++) g[0][i]=1;
for(int i=1;i<=n;i++){
int v,w;
scanf("%d%d",&v,&w);
//对于每一个物品体积,找到当前最大价值的时候,更新方案数
for(int j=0;j<=m;j++){
if(j<v){
f[i][j]=f[i-1][j];
g[i][j]=g[i-1][j];
//g[i][j]%=mod; 没有必要写
}
else{
f[i][j]=max(f[i-1][j],f[i-1][j-v]+w);
if(f[i-1][j]>f[i-1][j-v]+w) g[i][j]=g[i-1][j];
else if(f[i-1][j]<f[i-1][j-v]+w) g[i][j]=g[i-1][j-v];
else g[i][j]=g[i-1][j]+g[i-1][j-v];
g[i][j]%=mod;
}
}
}
printf("%d\n",g[n][m]);
return 0;
}
1.2优化掉一个维度
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010,mod=1e9+7;
int n,m;
int f[N],g[N];
int main(){
scanf("%d%d",&n,&m);
//因为是不少于的背包,所以不少于i的初始状态都有一种装法,就是啥也不装
for(int i=0;i<=m;i++) g[i]=1;
for(int i=1;i<=n;i++){
int v,w;
scanf("%d%d",&v,&w);
for(int j=m;j>=v;j--){
if(f[j]>f[j-v]+w) g[j]=g[j];
else if(f[j]<f[j-v]+w) g[j]=g[j-v];
else g[j]=g[j]+g[j-v];
g[j]%=mod;
f[j]=max(f[j],f[j-v]+w);
}
}
printf("%d\n",g[m]);
return 0;
}
2.背包是刚好等于
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010,mod=1e9+7;
int n,m;
int f[N],g[N];
int main(){
scanf("%d%d",&n,&m);
memset(f,-0x3f,sizeof f);
f[0]=0,g[0]=1;
for(int i=1;i<=n;i++){
int v,w;
scanf("%d%d",&v,&w);
for(int j=m;j>=v;j--){
if(f[j]>f[j-v]+w) g[j]=g[j];
else if(f[j]<f[j-v]+w) g[j]=g[j-v];
else g[j]=g[j]+g[j-v];
g[j]%=mod;
f[j]=max(f[j],f[j-v]+w);
}
}
//因为这里是背包刚好等于j,可能有j1!=j2但是f[j1]==f[j2]的情况,这两种都是答案得算上
int t=0;
for(int j=0;j<=m;j++) {
t=max(t,f[j]);
}
//最后求方案数
int ans=0;
for(int j=0;j<=m;j++){
if(t==f[j]) ans=(ans+g[j])%mod;
}
printf("%d\n",ans);
return 0;
}