很明显的一道完全背包板子题，做法也很简单，就是要注意
这里你可以买比所需多的干草，只要达到数量就行了
状态转移方程：dp[j]=min(dp[j],dp[j-m[i]]+c[i])
代码如下：
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<time.h>
using namespace std;
int h,n,m[],c[],dp[];
int main()
{
cin>>n>>h;
for(int i=;i<=n;i++)
{
cin>>m[i]>>c[i];
}
for(int i=;i<=h+;i++)
{
dp[i]=;
}
for(int i=;i<=n;i++)
{
for(int j=m[i];j<=h+;j++)
{
dp[j]=min(dp[j],dp[j-m[i]]+c[i]);
}
}
int ans=;
for(int i=h;i<=h+;i++)
{
ans=min(ans,dp[i]);
}
cout<<ans;
}
和0/1背包比较一下：
完全：
for(int i=;i<=n;i++)
{
for(int j=m[i];j<=h+;j++)
{
dp[j]=min(dp[j],dp[j-m[i]]+c[i]);
}
}
0/1
for(int i=1;i<=n;i++)
{
for(int j=m;j>=c[i];j--)
{
dp[j]=dp[j]+dp[j-c[i]];
}
}
有什么不一样呢？
我们可以发现，区别在于这两行：
/ for(int j=m;j>=c[i];j--)
完全 for(int j=c[i];j<=m;j++)//(这里是为了统一方便对比用一样的变量)
0/1是--，而完全是交换了0/1的位置并且变成++；
因为0/1背包每个都只能选择一次，而且dp[i]是由dp[i+1]推出的，即如果求dp[i]必需求dp[i+1]，所以从大到小；
而完全背包每个可以选的次数不限，dp[i]是由dp[i-1]推出的，故从小到大。