동적 프로그래밍을 통한 배낭 문제 이해
배낭 문제 종류 및 해결 방법
다양한 배낭 문제 유형과 그에 따른 최적화 전략을 정리합니다.
01 배낭 문제
n개의 물품(각각의 부피와 가치는 v[i], w[i])과 용량이 V인 배낭이 있을 때 최대 가치를 계산합니다.
for(int i=1; i=v[i]; --j)
dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
완전 배낭 문제
모든 물품이 무한히 제공되는 경우의 최적화 알고리즘입니 ...
7월 24일 01:33에 게시됨
2024년 하이베이 프로그래밍 경연 대회
A - 최대 곱셈
두 수 a와 b의 곱이 최대가 되는 조건은 a=1일 때입니다.
#include <iostream>
using namespace std;
typedef long long ll;
#define endl '\n'
ll gcd(ll a, ll b) {
while (b) {
swap(a, b);
b %= a;
}
return a;
}
void solve() {
ll x, y;
cin >> x >> y;
cout n;
vector points(n);
for (au ...
6월 23일 02:23에 게시됨