9도 1462:두 선박 적재물 문제(01배낭)

제목 설명:
n개의 물품의 무게와 두 척의 적재 무게가 각각 c1과 c2인 배를 정해 이 두 척의 배로 모든 물품을 실을 수 있느냐고 물었다.

사고의 방향
1. 수수한 가방 질문
2. 몇 가지 세부 사항을 잘 파악해야 한다. (1) 물품의 무게를 읽을 때 물품의 최대치와 총 무게를 통계하는 것을 포함한다(2) 적재 무게가 비교적 작은 배에 대해 dp를 계산한다.
3. 1차원 dp, dp[i]는 총 물품의 무게가 i일 때의 최대 가치를 나타내기 때문에 dp[i]는 연속적이지 않기 때문에 통계 결과를 집계할 때 dp를 두루 훑어야 한다.2차원 dp[][]는 행렬을 채울 수 있다

코드가 9도 테스트를 통과하지 못했습니다

#include <iostream> #include <stdio.h> #include <memory.h>
using namespace std; int n, c1, c2; int wet[200]; int dp[10000]; int main() { while(scanf("%d%d%d", &n, &c1, &c2) != EOF) { int totalWeight = 0; bool exceed = false; int biggerone = max(c1, c2); for(int i = 0; i < n; i ++) { scanf("%d", wet+i); totalWeight += wet[i]; if(wet[i] > biggerone) { exceed = true; } } if(exceed) { cout << "NO" << endl; continue; } int c = min(c1, c2); memset(dp, 0, sizeof(int)*totalWeight); for(int i = 0; i < n; i ++) { for(int v = c; v >= wet[i]; v --) { dp[v] = max(dp[v], dp[v-wet[i]]+wet[i]); } } int carryone; for(int i = 0; i <= c; i ++) carryone = max(carryone, dp[i]); if(biggerone >= totalWeight-carryone) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }

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

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

곤혹스러울 때 사용하는 문제 형식의 소개

포기할 수 있다면 그것도 방법이지만 일이라면 그렇게 하지 않을 거예요. 모르는 것을 묻기 위해 지식이 있는 사람에게 질문하겠죠. 처음부터 무언가에 대해 알려주면 심리적 모형을 만들어 줄 수 있다. 물어보고 싶은 것을...

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

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

9도 1462:두 선박 적재물 문제(01배낭)

좋은 웹페이지 즐겨찾기