HDU 3466 [DP 입문 01 가방]
오류는 다음과 같습니다.
(1) 상태 이동 방정식은 항상 dp[j-a[i]를 옮긴다.p]+a[i].v의 j는 m로 쓰이고 i는 j로 쓴다
이 문제:
아이템 수량 N과 수중 자금 M 제시
그리고 각 물품마다 가격 P를 주고 구매가 필요할 때 수중에 최소한 얼마의 자금이 필요한지 Q.현재 물품에 있는 당신의 돈 P는 반드시 Q보다 커야 합니다(따라서 P-Q<0의 것은 고려하지 않습니다).그리고 물건 자체의 가치 V
요구할 수 있는 최대 자금을 구하다
유일한 구덩이는 P-Q 서열입니다.
구조체로 하면 된다.제목에서 얼마 안 돼서 살 수 없다는 조건을 구조체가 보증했기 때문에 밥카드와 비슷하다
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std ;
struct node {
int p , q , v ;
}a[4000];
int dp[5000];
int cmp(node x ,node y)
{
return x.q-x.p<y.q-y.p;
}
int main()
{
int n , m , j , i;
while(cin>>n>>m)
{
for(i=0;i<n;i++)
{
cin>>a[i].p>>a[i].q>>a[i].v;
}
sort(a,a+n,cmp);
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
{
for(j=m;j>=a[i].q;j--)
{
if(dp[j]<dp[j-a[i].p]+a[i].v)
{
dp[j]=dp[j-a[i].p]+a[i].v;
}
}
}
cout<<dp[m]<<endl;
}
return 0 ;
}여러분, 안녕히 주무세요. QWQ 졸려 죽겠어요. 자동으로 빨개져요...
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
