我们记g[i][j]
为从前i
个物品中选择,恰好填满体积为j
的背包的方案数;
f[i][j]
为从前i
个物品中选择,体积为j
的背包最大可以装的物品的价值。
则有:
这里的合法指的是前面两个点分别对应的f值等于后面那个点的f值
结合代码理解:
for(int i=1;i<=n;i++){
int v,w; cin>>v>>w;
for(int j=t;j>=v;j--){
int maxv=max(f[j],f[j-v]+w);
int cnt=0;
if(maxv==f[j]) cnt=(cnt+g[j])%mod;
if(maxv==f[j-v]+w) cnt=(cnt+g[j-v])%mod;
g[j]=cnt%mod;
f[j]=maxv;
}
}
完整代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1005, mod = 1e9+7;
int n,t;
int f[N];
int g[N];
int main(){
cin>>n>>t;
g[0]=1;
for(int i=1;i<=n;i++){
int v,w; cin>>v>>w;
for(int j=t;j>=v;j--){
int maxv=max(f[j],f[j-v]+w);
int cnt=0;
if(maxv==f[j]) cnt=(cnt+g[j])%mod;
if(maxv==f[j-v]+w) cnt=(cnt+g[j-v])%mod;
g[j]=cnt%mod;
f[j]=maxv;
}
}
int ans=0;
for(int j=0;j<=t;j++)
if(f[j]==f[t]) ans=(ans+g[j])%mod;
cout<<ans<<endl;
return 0;
}