codevs 1155 김 명의 예산 안 - 심야 의 좌절 -

3823 단어 알고리즘
codevs 1155 김 명의 예산 안 - 심야 의 좌절 -
  • 오늘 의 마지막 순간 까지 나 는 이 문 제 를 풀 지 못 할 줄 은 생각 하지 못 했다.처음에는 첨부 파일 이 세 개 있 을 줄 알 았 는데 6 가지 조합 을 매 거 했 는데 코드 가 너무 지루 해서 이렇게 쓰 고 싶 지 않 았 다.그래서 잘못된 동적 계획 을 한 번 썼 습 니 다. 그 이 유 는 가방 문 제 를 잘 보지 못 했 기 때 문 입 니 다. 모든 아 이 템 을 선택 하거나 선택 하지 않 는 선택 에 대해 0 - V 의 모든 dp [i] 를 한 번 더 썼 습 니 다.
  • 나중에 참 지 못 하고 문 제 를 풀 었 습 니 다. 이른바 조합 가방 을 보 았 습 니 다. 저 는 바보 같이 모든 조합 을 새로운 물건 으로 새로운 배열 로 저 장 했 습 니 다. 그러나 이렇게 또 하나의 실 수 를 저 질 렀 습 니 다. 가장 좋 은 해 제 는 같은 메 인 부품 의 2 가지 서로 다른 조합 을 포함 할 수 있 습 니 다. 메 인 부품 이 문 제 를 보 는 것 보다 못 하고 생각 이 그렇게 간단 하 다 는 것 을 알 게 되 었 습 니 다.코드 가 그렇게 깔끔 해!한 번 의 업데이트 에서 4 가지 방안 (포함 되 지 않 음, 5 가지) 의 1 가 지 를 선택 하면 됩 니 다. 평소 템 플 릿 의 가방 은 1 가지 (선택 하지 않 으 면 2 가지 포함) 방안 중 하 나 를 선택 합 니 다.그룹 백 팩 은 처음 봤 어 요.
  • 문제 풀이 출처:http://codevs.cn/wiki/solution/?problem_id=1155 
    
#include 


#include 

using namespace std;
int f[40000],w[40000],v[40000],p[40000],s[40000][3];
int main()
{
   int n,m,k=0;

   scanf("%d%d",&m,&n);

   for(int i=1;i<=n;i++)
    {
       scanf("%d%d%d",&w[i],&v[i],&p[i]);
       v[i]=v[i]*w[i];//           *  
       if(p[i]!=0) s[p[i]][++s[p[i]][0]]=i;//  ，    
    }

   for(int i=1;i<=n;i++)
    if(p[i]==0)//      
     for(int j=m;j>=0;j--)
     {
       if(j-w[i]>=0)
        f[j]=max(f[j],f[j-w[i]]+v[i]);
       if(j-w[i]-w[s[i][1]]>=0&&s[i][1]!=0)
        f[j]=max(f[j],f[j-w[i]-w[s[i][1]]]+v[i]+v[s[i][1]]);
       if(j-w[i]-w[s[i][2]]>=0&&s[i][2]!=0)
        f[j]=max(f[j],f[j-w[i]-w[s[i][2]]]+v[i]+v[s[i][2]]);
       if((j-w[i]-w[s[i][1]]-w[s[i][2]])>=0)
        f[j]=max(f[j],f[j-w[i]-w[s[i][1]]-w[s[i][2]]]+v[i]+v[s[i][1]]+v[s[i][2]]);//    4   
     }
   printf("%d",f[m]);

   return 0;
}
    oh~

    • 백준 9184번 "신나는 함수 실행"
    [네트워크 흐름 24 문제 - 4] cogs 729 원탁 회식.

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage