ACM: 동적 기획, 01 가방 문제
n 개의 아 이 템 과 C 용량 의 가방 이 있 습 니 다.(모든 아 이 템 은 하나) i 번 째 아 이 템 의 부 피 는 v [i] 이 고 무 게 는 w [i] 입 니 다.일부 물품 을 골 라 이 가방 에 넣 으 면 가방 안의 물품 이 전체 부피 가 C 를 초과 하지 않 는 전제 에서 무 게 를 최대한 크게 할 수 있다.
해법: 두 가지 사고방식:
첫 번 째: d (i, j) 는 "i, i + 1, i + 2,... n 개 아 이 템 을 j 의 가방 에 담 은 다음 최대 총 중량" 이 라 고 밝 혔 다.
d(i, j) = max{d(i+1, j), d(i+1, j-v[i])+w[i]} 앞의 하 나 는 i 번 째 아 이 템 을 놓 지 않 는 다 는 뜻 이 고, 뒤의 하 나 는 i 번 째 아 이 템 을 놓 는 다 는 뜻 이다.그리고 둘 중 에 제일 큰 걸 로.
#include
#include
using namespace std;
const int MAXN = 10000;
int n, C, v[MAXN], w[MAXN];
int d[MAXN][MAXN]; //d(i, j) “ i,i+1,i+2,...n j ”
int main() {
cin >> n >> C;
for(int i = 0; i < n; ++i) {
cin >> v[i] >> w[i];
}
memset(d, 0, sizeof(d));
for(int i = n; i >= 1; --i) {
for(int j = 0; j <= C; ++j) {
d[i][j] = (i == n ? 0 : d[i+1][j]); // i
if(j >= v[i]) d[i][j] = max(d[i][j], d[i+1][j-v[i]]+w[i]); // i i
}
}
cout << d[1][C] << endl;
return 0;
} 두 번 째: d (i, j) 는 "앞의 i 개 물품 을 용량 이 j 인 가방 에 담 는 최대 총 중량" 이 라 고 밝 혔 다.
d(i, j) = max{d(i-1, j), d(i-1, j-v[i])+w[i]} 앞의 하 나 는 i 번 째 아 이 템 을 놓 지 않 는 다 는 뜻 이 고, 뒤의 하 나 는 i 번 째 아 이 템 을 놓 는 다 는 뜻 이다.그리고 둘 중 에 제일 큰 걸 로.
#include
#include
using namespace std;
const int MAXN = 10000;
int n, C;
int d[MAXN][MAXN]; //d(i, j) “ i j ”。
int main() {
cin >> n >> C;
memset(d, 0, sizeof(d));
int v, w;
for(int i = 1; i <= n; ++i) {
cin >> v >> w;
for(int j = 0; j <= C; ++j) {
d[i][j] = (i == 1 ? 0 : d[i-1][j]); // i
if(j >= v) d[i][j] = max(d[i][j], d[i-1][j-v]+w); // i i
}
}
cout << d[n][C] << endl;
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
