DP背包问题的 恰好装满 问题 ~~

背包问题中有时候会限定要 恰好装满。

先预定义一个无穷大（正）

#define INF 一个足够大的数

这里以恰好装满的01背包为例：

求最大值：

要求在恰好装满的情况下求最大值。

那么要对dp数组进行如下初始化：

	int dp[maxn];
	fill(dp,dp+maxn,-INF);
	dp[0]=0;     //如果是二维就把dp[0][0]~dp[n][0]初始化为0

那么最终若 dp[j] < 0，则说明容量为 j 的背包无法被恰好装满。

为什么这样可行呢? 可以模拟一下01背包的求解过程。

01背包状态转移方程： d p [ j ] = m a x { d p [ j − w [ i ] ] + c [ i ] , d p [ j ] ] } dp[j]=max\left \{ dp[ j-w[i] ]+c[i],dp[j]] \right \} dp[j]=max{dp[j−w[i]]+c[i],dp[j]]}$$(1\le i\le n,w[i]\le j\le V)$$

当 i == 1 时，判断第1件物品的装入

因为起初除dp[0]==0以外，所有dp[j]均为-INF，那么仅当 j == w[1] 时，可以令dp[j]不等于-INF。（其他情况下 dp[ j-w[1] ]+c[1] = -INF+c[i] = -INF　　　　　 PS.实际不真正等于-INF，但从数学角度来说，无穷大+常数=无穷大）

当 i == 2 时，判断第2件物品的装入

现在除 dp[0]==0 和 dp[w[1]]==c[1] 以外，所有 dp[i] 依旧为-INF，那么这时要么 j == w[2]，要么 j == w[1]+w[2]，才能令dp[j]不等于-INF。

以此类推…

所以最后dp[j]若还等于 -INF，就说明容量为 j 无法恰好装满。

这里很重要的一个点就是： 我们只是定义了一个负无穷大（-INF)，这实际还是个常数（一个负的足够大的常数）。从数学上来说最后还等于 -INF 就是无法恰好装满，但是这里并不是真正的负无穷大，可我们能保证最后它依旧 < 0。所以 最后的无法恰好装满的判断条件是：dp[j] < 0 。

求最小值：

实际上背包问题求最小值肯定是以恰好装满为前提的（不然什么都不装就是最小了）

同样的先对dp数组进行初始化：

	int dp[maxn];
	fill(dp,dp+maxn,INF);
	dp[0]=0;     //如果是二维就把dp[0][0]~dp[n][0]初始化为0

那么最终若 dp[j] == INF，则说明容量为 j 的背包无法被恰好装满。

状态转移方程也会变为：
d p [ j ] = m i n { d p [ j − w [ i ] ] + c [ i ] , d p [ j ] ] } dp[j]=min\left \{ dp[ j-w[i] ]+c[i],dp[j]] \right \} dp[j]=min{dp[j−w[i]]+c[i],dp[j]]}$$(1\le i\le n,w[i]\le j\le V)$$

总结：

①求最大值：

fill(dp,dp+maxn,-INF), dp[0]=0;

若 dp[j] < 0，说明容量为 j 的背包无法被装满；

②求最小值：

fill(dp,dp+maxn,INF), dp[0]=0;

若 dp[j] == INF，说明容量为 j 的背包无法被装满；