poj 2754/1014 다중 가방의 2진법 최적화

2754 문제: M(1<=M<=200)과 길이가 M인 네 개의 그룹을 정하고 각각 Pairs,Multi,Low,Up으로 기록한다. 당신은 길이가 M인 그룹 Table(그중 Low[i]<=Table[i]<=Up[i])를 구성하여 ∑Multi[i]*Table[i]=0을 만족시키고 ∑Pairs[i]*Table[i]를 최대한 크게 만들어야 한다.입력 만족은 최소한 하나의 해가 있다.
사고방식: 만약에 dp에 직접 올라가면 복잡도는 최대 M*극차*50에 달한다.그 중에서 M은 서열 길이이고 50은 개당 최대 50개의 수치를 얻을 수 있기 때문에 극차는 ∑Multi[i]*Table[i]가 도달할 수 있는 최대치와 최소치 사이의 차이이다.감당할 수 없다.다중 가방으로 전환하는 문제를 고려해 보겠습니다.
하계를 따로 꺼내 일부로 계산하기 때문에 [Low[i], Up[i]]는 [0, U[i]-L[i]]의 다중 가방으로 전환된다.M[i]와 P[i]는 모두 별도의 하계 계산을 한다.T = L[1] *M[1] + L[2] *M[2]을 계산하여....그 다음은 용량 T가 마침 가득 찬 다중 가방이다.
다중 가방은 이진 최적화가 있습니다. 참고(http://www.cnblogs.com/favourmeng/archive/2012/09/07/2675580.html).

#include 
#include 
#include 
#define N 205
#define ORI 50000
#define INF 0x7fffffff
using namespace std;
int dp[200005];
int n,m;
int up[N],low[N],p[N],w[N];
int main(){
    while(scanf("%d",&n) != EOF){
        m = 0;
        int presum = 0;
        for(int i = 0;i num){
                for(int j = m;j>=num*w[i];j--)
                    dp[j] = max(dp[j], dp[j-num*w[i]]+num*p[i]);
                up[i] -= num;
                num <<= 1;
            }
            for(int j = m;j>=up[i]*w[i];j--)
                dp[j] = max(dp[j], dp[j-w[i]*up[i]]+p[i]*up[i]);
        }
        printf("%d
",dp[m]+presum);
        
    }
    return 0;
}

1014제의: 여섯 종류의 돌이 있는데 각각 1~6의 가치가 있고, 현재는 각각 1~6의 돌의 수량(돌의 총수는 20000을 넘지 않는다)을 제시한다.이 돌들을 두 종류로 나누어 각각의 가치를 총합할 수 있느냐고 물었다.
사고방식: 우선 가치의 총화를 구하고 기수라면 반드시 안 된다.그렇지 않으면 다중 배낭 문제가 되어 총화의 절반을 모을 수 있는지 2진법으로 최적화할 수 있는지를 보게 된다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define N 120005
#define INF 0x3fffffff
int s[7],c = 1;
bool dp[N>>1];
using namespace std;
int main(){
    while(1){
        int m = 0;
        for(int i = 1;i<=6;i++){
            scanf("%d",&s[i]);
            m += i*s[i];
        }
        if(m == 0)
            break;
        if(m & 1)
            printf("Collection #%d:
Can't be divided.

",c++);
        else{
            memset(dp,false,sizeof(dp));
            dp[0] = true;
            m >>= 1;
            for(int i = 1;i<=6;i++){
                if(!s[i])
                    continue;
                int num = 1;
                while(s[i] > num){
                    for(int j = m;j-num*i>=0;--j)
                        dp[j] |= dp[j - num*i];
                    s[i] -= num;
                    num <<= 1;
                }
                for(int j = m; j - s[i]*i>=0; --j)
                    dp[j] |= dp[j - s[i]*i];
            }
            if(dp[m])
                printf("Collection #%d:
Can be divided.

",c++);
            else
                printf("Collection #%d:
Can't be divided.

",c++);
        }
    }
    return 0;
}

poj 2754/1014 다중 가방의 2진법 최적화

좋은 웹페이지 즐겨찾기