가방 문제

01 가방 질문 - dp


제목 설명:
n개의 물품이 있는데 각각의 부피와 가치가 있습니다. 현재 주어진 용량의 배낭은 어떻게 배낭에 넣은 물품이 가장 큰 가치를 가지게 합니까?
샘플 입력: [4는 아이템 개수, 8은 부피 크기, 아래 4행은 i번째 아이템의 부피와 가치] 4, 8, 2, 3, 4, 4, 5, 6.
샘플 출력: 10
AC 코드:
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int dp[10005][10005];
int value[10005],w[10005];//     i          
int main()
{
	int n,v,i,j;
	cin>>n>>v;
	for(i=1;i<=n;i++) 
		cin>>w[i]>>value[i];
	//dp[i][j]:     i   ,     j      
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=v;j++)
		{
			if(j<w[i])
				dp[i][j]=dp[i-1][j];
			else
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+value[i]);
		}
	}
	cout<<dp[n][v]<<endl;
	return 0; 
} 

좋은 웹페이지 즐겨찾기