北航算法第三次练习赛-零崎的朋友很多Ⅱ | Eternal_zttz

北航算法第三次练习赛-零崎的朋友很多Ⅱ

致敬DP

解题思路

同样,这也是一道01背包问题,所不同的是,它需要最后是分文不剩,即相当于最终的结果是背包需要完全放满,对于这种问题,我们只需要对初始化做一点小小的改变,即除了f[0] = 0外,其它f[]数组值均设置为-1,这样,我们就可以保证f[v]为恰好装满背包时的最优解。

这是为什么呢,我们可以这样考虑:初始化的f[]数组事实上对应的就是在没有任何物品可以放入背包时的合法状态,如果要求背包恰好装满,那么此时只有容量为0的背包可以在什么都不装且价值为0的情况下被“恰好装满”,其它情况都没有合法的解,所以我们可以把他们看作未定义的状态。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstring>
const int N = 20010;
int v[N],w[N],f[N];
int main(){
int t,k;
while(~scanf("%d %d",&t,&k)){
memset(v, 0, sizeof(v));
memset(w, 0, sizeof(w));
memset(f, -1, sizeof(f));
f[0] = 0;
for (int i = 0;i<k;i++)
scanf("%d %d",&v[i],&w[i]);
for (int i = 0;i<k;i++){
for (int j = t;j>=w[i];j--){
if(f[j]<f[j-w[i]]+v[i]&&f[j-w[i]]!=-1)
f[j] = f[j-w[i]]+v[i];
}
}
if(f[t] == -1)
printf("jpx\n");
else printf("%d\n",f[t]);
}
}
-------------The End-------------