hdu1114 完全背包

题目链接：https://vjudge.net/problem/HDU-1114
转自：https://www.cnblogs.com/littlehoom/p/3550906.html
题意：有一个存储罐，输入空时重量与满载重量，有几种钱币，输入价值与重量，求存储罐满载时的最小价值。
思路：完全背包+一维优化。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int dp[maxn],v[505],w[505];
const int inf=0x3f3f3f;
int main()
{
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
memset(dp,inf,sizeof(dp));
dp[0]=0;
int w1,w2;
cin>>w1>>w2;
w1=w2-w1;
int n;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>v[i]>>w[i];
}
for(int i=0; i<n; i++)
{
for(int j=w[i]; j<=w1; j++)
{
dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
}
}
if(dp[w1]<inf)
{
cout<<"The minimum amount of money in the piggy-bank is "<<dp[w1]<<".n";
}
else
{
cout<<"This is impossible.n";
}
}
return 0;
}

最后

以上就是开放柜子为你收集整理的hdu1114 完全背包的全部内容，希望文章能够帮你解决hdu1114 完全背包所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。