hdu 3033 I love sneakers!(DP)
제목 의미
조별 가방 문제, 대의**신발을 사야 합니다. k가지 브랜드가 있고 각 브랜드는 적어도 신발 한 켤레를 사야 합니다.신발마다 표시 가격과 실제 가치가 있다.m이 넘는 돈으로 가장 값진 신발을 사세요.사실 나는 이 문제의 난점이 적어도 이 점을 처리하는 데 있다고 생각한다.상태방정식은 많은 사람들이 dp[k][m]로 이미 k종의 신발을 샀는데 m돈이 있는 상태의 신발의 최대 가치를 나타낼 수 있다.상태 전이 방정식은 for(k=1;k <=K;k++) {for(i=0;i
#include"stdio.h"
#include"string.h"
#define max(x,y) x>y?x:y;
int dp[11][10001];
int main()
{
int N,M,K,i,j,k;
int cost[11][101],value[11][101],a,b,c,num[11];
while(scanf("%d%d%d",&N,&M,&K)!=-1)
{
memset(dp,-1,sizeof(dp));
memset(num,0,sizeof(num));
for(i=0;i<N;i++)
{
scanf("%d%d%d",&a,&b,&c);
cost[a][num[a]]=b;
value[a][num[a]]=c;
num[a]++;
}
for(i=0;i<M;i++)
dp[0][i]=0;
for(i=1;i<=K;i++)
{
for(j=0;j<num[i];j++)
{
for(k=M;k>=cost[i][j];k--)
{
// 。。
if(dp[i][k-cost[i][j]]!=-1)
dp[i][k]=max(dp[i][k],dp[i][k-cost[i][j]]+value[i][j]);
if(dp[i-1][k-cost[i][j]]!=-1)
dp[i][k]=max(dp[i][k],dp[i-1][k-cost[i][j]]+value[i][j]);
}
}
}
if(dp[K][M]==-1)
printf("Impossible
");
else
printf("%d
",dp[K][M]);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
