hdu 3449 Consumer(ＤＰ)
제목배낭에 의지하다.
물건을 살 때는 반드시 그에 상응하는 상자를 먼저 사야 한다.그리고 n개 상자의 가격과 이 상자에 담을 수 있는 물품의 가격과 가치.
최대의 가치를 추구합니다!!
일반:
ｄｐ［ｉ］［ｊ］＝ｄｐ［ｉ］［ｊ－ｃｏｓｔ［ｉ］］＋ｖａｌｕｅ［ｉ］;
상자의 가치를 고려해야 한다.까닭
ｄｐ［ｉ］［ｊ］＝ｍａｘ(ｄｐ［ｉ－１］［ｊ］,ｍａｘ(ｄｐ［ｉ－１］［ｊ－ｋ］＋ｐａｃｋ［ｉ］［ｋ］));
그 중에서 dp[i][j]는 전 i개의 상자를 사용하여 j가 얻은 최대 가치를 나타낸다.i번째 상자를 도대체 고를지 안 고를지 고려하면 얼마를 더 써야 하는지 시간 복잡도가 높기 때문에 최적화한다.
자세히 분석하면 dp[i-1][j-k]+pack[i][k]가 i번째 상자를 고려하는 상황에서 가장 큰 가치를 발견할 수 있다.
상자의 가치를 0으로 간주하고 금전j에서 먼저 상자의 가격을 고려하면 나머지는 상자 속의 물품, 즉 01배낭만 고를 수 있다.
f(i, j)를 이전 i개의 상자로 하고 i개를 반드시 고려한 상황에서 가장 큰 가치로 초기화하기 때문에 f(i, j)=max(f[i][j-box[i]+0)(PS: 초기화하면 상자의 영향이 없어진다).그리고 01이면 돼!
#include"stdio.h"
#include"string.h"
#define max(x,y) x>y?x:y;
int dp1[100001];
int dp2[100001];
int main()
{
int n,w,i,j,k;
int cost[55][11],value[55][11];
int num[55],box[55];
while(scanf("%d%d",&n,&w)!=-1)
{
for(i=1;i<=n;i++)
{
scanf("%d",&box[i]);
scanf("%d",&num[i]);
for(j=1;j<=num[i];j++)
scanf("%d%d",&cost[i][j],&value[i][j]);
}
memset(dp1,0,sizeof(dp1));
for(i=1;i<=n;i++)
{
for(j=w;j>=box[i];j--)
dp2[j]=dp1[j-box[i]];／／ ， ！！
for(j=1;j<=num[i];j++)
{
for(k=w;k>=cost[i][j]+box[i];k--)
dp2[k]=max(dp2[k],dp2[k-cost[i][j]]+value[i][j]);
}
for(j=w;j>=box[i];j--)
dp1[j]=max(dp1[j],dp2[j]);／／ ｄｐ１
}
printf("%d
",dp1[w]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
