[HDU 1171] 빅 이벤트 in HDU 모 함수 또는 멀 티 백 팩
제목: 항 전 컴퓨터 대학 은 분가 하여 물건 을 두 몫 으로 나 누 어 두 몫 의 가치 가 가장 가 까 워 야 한다.먼저 아 이 템 수량 n 을 입력 하면 n 개의 아 이 템 이 있 음 을 표시 하고 각 아 이 템 의 가치 와 수량 을 입력 합 니 다.구 덩이 를 비교 하 는 곳 은 입력 음수 가 끝 나 는 것 이다.
사고: 모 함수 또는 다 중 가방
모 함수 코드 (514 ms):
#include
#include
#include
using namespace std;
int val[55],counts[55];
int nex[125005], temp[125005];
int main()
{
int n;
while(cin>>n && n >= 0)
{
int sum = 0;
for(int i = 0; i < n; i++){
cin>>val[i]>>counts[i];
sum += val[i]*counts[i];
}
int avg = sum / 2;
memset(nex, 0, sizeof(nex));
memset(temp, 0, sizeof(temp));
for(int i = 0; i <= counts[0]; i++){
nex[i * val[0]] = 1;
}
int len = val[0] * counts[0];
for(int i = 1; i < n; i++){
for(int j = 0; j <= len && j <= avg; j++){
for(int k = 0; k <= val[i]*counts[i] && j+k <= avg; k += val[i]){
temp[j+k] += nex[j];
}
}
len += val[i]*counts[i];
for(int j = 0; j <= len && j <= avg; j++){
nex[j] = temp[j];
temp[j] = 0;
}
}
for(int i= avg; i >= 0; i--){
if(nex[i] != 0){
cout<" "<break;
}
}
}
return 0;
}
다 중 가방 (93ms):
#include
#include
#include
#include
#include
#include
using namespace std;
int dp[125005];
void ZeroOnePack(int volume, int val, int vol)
{
for(int i = volume; i >= vol; i--){
dp[i] = dp[i-vol] + val;
}
}
void CompletelyPack(int volume, int val, int vol)
{
for(int i = vol; i <= volume; i++){
dp[i] = dp[i-vol] + val;
}
}
void MultiplePack(int volume, int val, int vol, int counts)
{
if(vol * counts > volume)
CompletelyPack(volume, val, vol);
int mid = 1;
while(mid <= counts){
ZeroOnePack(volume, val*mid, vol*mid);
counts = counts - mid;
mid = mid << 1;
}
if(counts){
ZeroOnePack(volume, val*counts, vol*counts);
}
}
int main()
{
int n;
int val[55],counts[55];
while(cin>>n && n >= 0)
{
int sum = 0;
memset(dp, 0, sizeof(dp));
for(int i = 0; i < n; i++){
cin>>val[i]>>counts[i];
sum += val[i]*counts[i];
}
for(int i = 0; i < n; i++){
MultiplePack(sum/2, val[i], val[i],counts[i]);
}
cout<2]<<" "<2]<return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
124. 두 갈래 나무의 최대 경로와 leetcode비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다. 본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.