[DP 복습3-완전배낭] HDU 1114-Piggy-Bank

1326 단어
제목: 클릭하여 링크 열기
완전 가방, 0-1 가방과 달리 두 번째 훑어보는 순서입니다. 거꾸로 하면 돼요. 최소치를 구하면 MIN으로 바꾸고 다른 건 변함이 없어요.
또한 초기화된 값에 주의해야 한다.제목은 적당히 채워야 하고 요구하는 값은 최대한 작아야 하기 때문에 dp[0]를 0으로 하고 나머지는 무한대(적당히 채워야 한다는 요구가 없으면 모두 0)로 한다.
마지막으로 판단할 때 처음에 준 값을 빼는 것을 잊지 마라.
#include <iostream>
#include <cstring>
using namespace std;

const int INF=0x7FFFFFF;
int dp[100005];
int value[1000],weight[1000];

int min(int a,int b)
{
	if(a<=b)
		return a;
	else
		return b;
}

int main()
{
	int testcase;
	int needweight,totalmoney,pignum;
	cin>>testcase;
	while(testcase--)
	{
		memset(value,0,sizeof(value));
		memset(weight,0,sizeof(weight));
		for(int i=1;i<100005;i++)
		{
			dp[i]=INF;
		}
		dp[0]=0;


		cin>>needweight>>totalmoney;
		cin>>pignum;
		for(int i=0;i<pignum;i++)
		{
			cin>>weight[i]>>value[i];
		}
		
		totalmoney-=needweight;//        
		
		for(int i=0;i<pignum;i++)
		{
			for(int j=value[i];j<=totalmoney;j++)
			{
				dp[j]=min(dp[j],dp[j-value[i]]+weight[i]);
			}
		}
			if(dp[totalmoney]!=INF)
			{
				cout<<"The minimum amount of money in the piggy-bank is "<<dp[totalmoney]<<"."<<endl;
			}
			else
				cout<<"This is impossible."<<endl;
		
		
	}
		
	return 0;
}

좋은 웹페이지 즐겨찾기