hdu 1171 Big Event in HDU 백팩/동적 계획
4549 단어 event
N개 물품, 매 물품의 가치는 a[i]이고 수량은 b[i]입니다. 두 무더기로 나누면 차액이 최대한 적습니다.
문제풀이의 방향
다중 가방의 변형인 것 같아요~~~
상태 DP[N][V]는 앞의 i개 물품, 가치가 V인 방안의 수를 나타낸다
전이 방정식
dp[i][ j+k*a[i] ] += dp[i-1][j] //k = 0..b[i]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int N = 250010;
int dp[2][N];
int main(){
int a[110], b[110], n;
while( scanf("%d",&n) != EOF){
if( n < 0 ) break;
memset( dp, 0, sizeof(dp));
dp[0][0] = 1;
int V = 0;
for(int i = 1; i <= n; i++){
scanf("%d%d",a+i,b+i);
V += a[i]*b[i];
}
for(int i = 1; i <= n; i++){ // 50
int cur = (i+1)&1, nxt = i&1;
memset( dp[nxt], 0, sizeof(dp[nxt]));
for(int j = 0; j <= V; j++){ // 250000
for(int k = 0; k <= b[i] && (k*a[i]+j)<=V; k++) //100
dp[nxt][ k*a[i]+j ] += dp[cur][j];
}
}
for(int i = V/2; i <= V; i++){
if( dp[n&1][i] ){
int ans = (i>V-i)?i:V-i;
printf("%d %d
", ans, V-ans );
break;
}
}
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
앱에서 KSP 출력 사용: 4부이제 생성된 클래스가 있으므로 코드에서 사용해 보겠습니다. Checkout other parts in this series: Android KSP guide for dummies by a Dummy: Part 1 (...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
