背包问题的恰好装满问题

背包问题的恰好装满问题

在一些背包问题中要求会从不超过背包最大容量变为恰好装满背包，与前者的差别在于初始化的不同

1. 在恰好装满的情况下取最大值

把dp[maxn]全赋值为-INF
dp[0]=0;
如果dp[n]<0，则在容量为n时，背包无法装满。
恰好装满的dp[n]有一个具体值，而不是-INF

memset(dp,-INF,sizeof(dp));
dp[0]=0;

注意
INF的取值并不是越大越好，INF过大会有溢出问题，一般在int32位整数数据时INF取0x3f3f3f3f

2.在恰好装满的情况下去最小值

把dp[maxn]全赋值为INF
dp[0]=0;
如果dp[n]>0，则在容量为n时，背包无法装满。
恰好装满的dp[n]有一个具体值，而不是INF

memset(dp,INF,sizeof(dp));
dp[0]=0;

• 当不需要背包恰好装满时
  dp数组初始化的值全为0。

在二维数组初始化的时候
dp[0][0]=0;
第一行和第一列的值都赋为INF