01背包最优决策方案数
-
两个dp数组:
$f[j]$ 表示背包容积”恰好”为j时的最大价值和 ———— 最优解dp
$g[j]$ 表示背包容积”恰好”为j时取最优解的方案数 ———— 方案数dp
两个数组通过下标j相对应 -
最后找到最优解的数值,在$g[j]$里面只要与这个数相等的都是最优方案数
-
注意:
因为最终不一定占满全部的背包体积,所以最优解不一定是$f[m]$
01背包在这个地方就不一样了,因为01背包就算占不满m的体积到最后也可以转移到$f[m]$中,$f[m]$保留的就是最优解
但是方案数中$g[j]$严格与$f[i]$相对应,必须找出准确的取最优解时的体积
注意定义的这个“恰好” -
初始化:
$g[0] = 1;//啥都不选也算一种方案 $
$f[i] = 0;$
$f[1~n] = -INF;$
CODE
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int mod = 1e9+7;
const int INF = 1e9;
const int N = 10001;
int n,m,f[N],g[N];
int w[N],v[N];
void init(){
g[0] = 1;
f[0] = 0;
for(register int i=1; i<=m; i++) f[i] = -INF;
}
int main() {
scanf("%d%d",&n,&m);
init();
for(register int j=1; j<=n; j++) scanf("%d%d",&w[j],&v[j]);
for(register int i=1; i<=n; i++) {
for(register int j=m; j>=w[i]; j--){
int tmp = max(f[j], f[j-w[i]]+v[i]);
int s = 0;
if(tmp==f[j]) s += g[j];
if(tmp==f[j-w[i]]+v[i]) s += g[j-w[i]];
//这里不能写else if,因为若两决策的答案一样,要把两种决策的方案都算上
f[j] = tmp;
g[j] = s%mod;
}
}
int maxn=0, ans=0;
for(register int i=1; i<=m; i++) maxn = max(maxn,f[i]);
for(register int i=1; i<=m; i++) {
if(maxn==f[i]) {
ans += g[i];
ans %= mod;
}
}
printf("%d\n",ans);
return 0;
}
可用*max_element取最大值
res并不用循环找,f[m]不就是f[res]嘛,可以不用循环找的吧?
状态设置为:f[j]表示背包容积”恰好”为j时的最大价值,那么显然f[m]不一定是最大,只能是体积恰好为m最大。
题目说的是总体积不超过m的最大值
点赞点赞hh
嘿嘿