题目链接
洛谷 P2918 [USACO08NOV] Buying Hay S
Tip：约翰与 FJ 为同一人。
F1：特殊完全背包
以往的背包都是求最大值，但在这道题中，由于限制条件为大于，且价值最大值过大，所以还是只能对大于等于 \(H\) 磅这一条件 入手。考虑更改状态定义。定义 \(dp_j\) 表示至少 \(j\) 磅干草所需美元，则同理对于 \(j>p_i\) 的部分，状态转移方程如下，其中 \(i\) 枚举干草，\(j\) 正序枚举干草磅数。
而对于 \(j\le p_i\) 的部分，根据定义，要么买这种干草，需要 \(c_i\) 美元；要么不买，则仍为 \(p_i\)。所以状态转移方程如下，\(i,j\) 含义同上。
初始化中，只需提前对每个 \(dp_j\) 赋最大值即可，代码如下，时间复杂度 \(O(nH)\)。
#include<bits/stdc++.h>
using namespace std;const int N=105,M=50010;
int n,h;
int p[N],c[N],dp[M];int main(){scanf("%d%d",&n,&h);for (int i=1;i<=n;++i) scanf("%d%d",p+i,c+i);memset(dp,0x3f,sizeof dp);for (int i=1;i<=n;++i){for (int j=1;j<=p[i];++j) dp[j]=min(dp[j],c[i]);for (int j=p[i]+1;j<=h;++j) dp[j]=min(dp[j],dp[j-p[i]]+c[i]);}printf("%d",dp[h]);return 0;
}
F2：特殊背包+当前体积拓展
上面的状态转移方程 \(dp_j=\min{(dp_j,dp_{j-p_i}+c_i)}\) 是由前面的状态推出当前干草磅数 \(j\)，但问题本身也可以看成以当前干草磅数 \(j\) 拓展出去，如果再买一捆当前干草，磅数变为 \(j+p_i\)，花费增加 \(c_i\)。所以对于 \(j+p_i\le H\) 的部分状态转移方程如下，\(i,j\) 含义同上。
对于 \(j+p_i>H\) 的部分，根据定义，也可以转变为为干草磅数至少为 \(H\) 的状态，即 \(dp_H\)，状态转移方程如下。
初始化同理，只需额外令 \(dp_0=0\)，时间复杂度不变，注意 \(j\) 的范围变化。
#include<bits/stdc++.h>
using namespace std;const int N=105,M=50010;
int n,h;
int p[N],c[N],dp[M];int main(){scanf("%d%d",&n,&h);for (int i=1;i<=n;++i) scanf("%d%d",p+i,c+i);memset(dp,0x3f,sizeof dp);dp[0]=0;for (int i=1;i<=n;++i){for (int j=0;j<=h;++j){int k=min(j+p[i],h);dp[k]=min(dp[k],dp[j]+c[i]);}}printf("%d",dp[h]);return 0;
}
F3：背包求最小值+增加背包范围
由于题目中问至少，所以普通的完全背包无法直接套用。但至少肯定有个上限，观察到如果现在已经有 \(j\) 磅干草，遍历至第 \(i\) 捆，那么如果 \(k\) 为满足 \(j+p_i*k\le H\) 的最大值，则购买 \(j+p_i*(k+1)\) 磅干草仍可能可以更新答案，但是对于购买 \(j+p_i*(k+2)\) 磅及以上干草，其花费肯定比购买 \(j+p_i*(k+1)\) 磅干草多，不可能更新答案，无需遍历。所以上限即为 \(h+c_i\)，由题目得为 \(55000\)。其余的按照常规完全背包去做即可。
#include<bits/stdc++.h>
using namespace std;const int N=105,M=55010,C=5000;
int n,h;
int p[N],c[N],dp[M];int main(){scanf("%d%d",&n,&h);for (int i=1;i<=n;++i) scanf("%d%d",p+i,c+i);memset(dp,0x3f,sizeof dp);dp[0]=0;for (int i=1;i<=n;++i){for (int j=p[i];j<=h+C;++j) dp[j]=min(dp[j],dp[j-p[i]]+c[i]);}int ans=INT_MAX;for (int i=h;i<=h+C;++i) ans=min(ans,dp[i]);printf("%d",ans);return 0;
}
总结
这题关键点在于如何从条件中推出新的可以使用的限制，以此为抓手进行解题。