가방 문제 구 안 수
있다 N 물품 과 용량 은? V 라 는 가방 을 들 었 다.각 아 이 템 은 1 회 만 사용 할 수 있 습 니 다.
제. i 물건 의 부 피 는? 가치 wi。
어떤 물건 을 가방 에 넣 으 면 이 물건 들 의 총 부피 가 가방 용량 을 초과 하지 않 고 총 가치 가 가장 큽 니까?
출력 최 우선 선택 법의 방안 수.정 답 이 클 수 있 으 니 정 답 모드 를 출력 하 십시오. 1e9 + 7 의 결과.
입력 형식
첫 줄 의 두 정수, N, V 는 빈 칸 으로 분리 하여 각각 물품 수량 과 가방 용적 을 나타 낸다.
다음 N 줄, 줄 마다 두 개의 정수 vi, wi 는 빈 칸 으로 나 누 어 각각 1 등 을 나타 낸다. i 물품 의 부피 와 가치.
출력 형식
정수 출력 프로젝트 수 모형. 1e9 + 7 의 결과.
데이터 범위
0 0
입력 샘플
4 5
1 2
2 4
3 4
4 6
출력 예시:
2하나의 배열 cnct 가 최대 가 치 를 기록 하 는 방안 수
왜 많은 문제 들 이 1e9 + 7 을 모 아야 합 니까? 모 의 대수 와 모 의 질 수 는 충돌 을 줄 일 수 있 습 니 다.
예 를 들 어 모든 결과 가 짝수 라면....................................................................................
한편, 모델 1e9 + 7 은 또 하나의 좋 은 특징 이 있 는데 그것 이 바로 int 를 폭발 시 키 지 않 고 상승 하여 롱 롱 롱 롱 을 폭발 시 키 지 않 는 다 는 것 이다.
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] volume = new int[N];
int[] value = new int[N];
for(int i = 0; i < N; i++){
volume[i] = sc.nextInt();
value[i] = sc.nextInt();
}
int[] dp = new int[V+1];
int[] cnt = new int[V+1];
Arrays.fill(cnt,1);
int mod = (int)1e9+7;
for(int i = 0; i < N; i++){
for(int j = V; j >= volume[i]; j--){
if(dp[j-volume[i]]+value[i] > dp[j]){
dp[j] = dp[j-volume[i]]+value[i];
cnt[j] = cnt[j-volume[i]]%mod;
}
else if(dp[j-volume[i]]+value[i]==dp[j]){
cnt[j] = (cnt[j]+cnt[j-volume[i]])%mod;
}
}
}
System.out.print(cnt[V]) ;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
