这个问题的原型就是完全背包问题模型，所不同的是完全背包问题要求的是最大价值，而这个是最小价值
完全背包问题的模型代码是
for (int i = 1; i <= n; ++ i)for (int j = c[i]; j <= v; ++ j)dp[j] = max(dp[j - c[i]] + w[i], dp[j]);明确了这个模型是完全背包问题，我们再来确定初始状态，dp数组的初始状态，dp[0]应该是0，dp[1-m]都INF，原因是想用硬币更新其值，不然就是一个硬币都没有放入。(感觉类比求一个数组的最小值比较好理解这里的初始化INF的处理)
既然是求得最小价值，那么状态转移方程应该是dp[j]=min(dp[j-c[i]+w[i],dp[j]);
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
const int N=10005;
int dp[N];
int val[N];
int weight[505];int main()
{int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;++i){scanf("%d%d,",&val[i],&weight[i]); //读入每件物品的价值和重量}for(int i=1;i<=m;++i)dp[i]=INF; //初始条件for(int i=1;i<=n;++i){for(int j=weight[i];j<=m;++j){dp[j]=min(dp[j-weight[i]]+val[i],dp[j]); //转移状态方程}}if(dp[m]==INF)printf("impossible");elseprintf("%d\n",dp[m]);}return 0;
}