hdu 3159 FATE (2 차원 비용 배낭 판 문제)

제목: 누 드 제목 으로 가방 9 에 적 힌 2 차원 비용 공식 과 똑같다.
문제.
2 차원 비용 의 가방 문 제 는 모든 물품 에 대해 두 가지 서로 다른 공간 소 비 를 가지 고 이 물품 을 선택 할 때 반드시 이 두 가지 대 가 를 동시에 지불해 야 한 다 는 것 을 말한다.모든 대 가 는 지불 할 수 있 는 최대 치 (가방 용량) 가 있다.아 이 템 을 선택 하면 가장 큰 가 치 를 얻 을 수 있 는 방법 을 묻는다.이 두 가지 대 가 를 각각 대가 1 과 대가 2 로 설정 하고, i 번 째 물품 에 필요 한 두 가지 대 가 는 각각 Ci 와 Di 이다.두 가지 대가 로 지불 할 수 있 는 최대 치 (두 가지 가방 용량) 는 각각 V 와 U 다.물품 의 가 치 는 Wi
알고리즘
비용 은 1 차원 을 더 하고 상태 도 1 차원 만 더 하면 된다.F [i, v, u] 를 설정 하면 앞의 i 개 물품 이 두 가지 대 가 를 치 르 면 각각 v 와 u 일 때 얻 을 수 있 는 최대 가치 임 을 나타 낸다.상태 이동 방정식 은 바로 F [i, v, u] = max {F [i - 1, v, u], F [i - 1, v - Ci, u - di] + Wi} 이다. 상기 공간 복잡 도 를 최적화 하 는 방법 은 2 차원 배열 만 사용 할 수 있다. 모든 물건 을 한 번 만 찾 을 수 있 을 때 변수 v 와 u 는 역순 으로 순환 하고 물품 이 가방 문제 와 같 을 때 순서 적 인 순환 을 하 며 물품 이 다 중 가방 문제 가 있 을 때 물품 을 나 눌 수 있다.

#include 
#include 
#include 
#include  
using namespace std;
const int maxn = 1005;
int n, m, s, k;
int dp[maxn][maxn];
int a[maxn], b[maxn];
int main() {
    while(~scanf("%d%d%d%d", &n, &m, &k, &s)) {
        for(int i = 1; i <= k; i++) {
            scanf("%d%d", &a[i], &b[i]);
        }
        memset(dp, 0, sizeof(dp));
        for(int q = 1; q <= k; q++) {
            for(int i = b[q]; i <= m; i++) {
                for(int j = 1; j <= s; j++) {
                    dp[i][j] = max(dp[i][j], dp[i - b[q]][j - 1] + a[q]);
                }
            }
        }

        int flag = -1;
        for(int i = m; i >= 1; i--) {
                if(dp[i][s] >= n) {
                    flag=max(flag,m-i);
                }
        }
        printf("%d
", flag);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

DP_동전 문제

한 문 제 를 읽 고 해결 하려 고 할 때 먼저 그 제한 을 살 펴 보 자.여러 시간 안에 해결 하 라 고 요구 하면 이 문 제 는 DP 로 풀 어야 할 가능성 이 크다.이런 상황 에 부 딪 히 면 가장 중요 한 것...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

hdu 3159 FATE (2 차원 비용 배낭 판 문제)

좋은 웹페이지 즐겨찾기