hdu 2844 coins(다중 가방 + 바이너리 최적화)

1895 단어
n가지 액면가의 동전과 그것들의 수량을 제시하고 m를 초과하지 않는 액면가를 구성할 수 있는 동전이 몇 개냐고 묻는다.
예제 2 설명:
2 5
1 4 2 1
액면가 1의 동전 2개, 액면가 4의 동전 1개.구성할 수 있는 액면가는 1, 2, 4, 5, 6이다.이 중 액면가 5를 넘지 않는 액면가는 4개다.
전형적인 다중 가방 문제.
이곳의 액면가는 가방 문제 중의 물품의 부피와 물품의 가치에 해당한다.
따라서 dp[i]는 i를 초과하지 않는 최대 액면가, 즉 dp[i]<=i를 나타낸다. 특정한 액면가 k에 대해 i>k와 dp[i]=k가 있으면 그 전에 반드시 dp[k]=k가 있다.
최종적으로 답안을 통계할 때 1부터 m까지 한 번 훑어보고 dp[i]=i의 액면가 i의 수량을 통계하면 된다. 이렇게 하면 구성할 수 있는 각종 액면가가 딱 한 번만 통계될 수 있다.
2진법의 최적화는 사실 2진법의 원리를 이용하여 같은 종류의 물품의 수량을 구분하는 것이다.여러 개의 동종 물품을 하나의 물품으로 간주하는데 그 가치는 원가치 곱하기 위에 구분된 수량이고 부피는 원체적 곱하기 위에 구분된 수량이다.
그리고 문제를 0-1 가방으로 바꾸어 해답을 구합니다.0-1 가방으로 직접 전환하는 것보다 시간 복잡도는 O(V*sum)에서 O(V*(log(sum))로 최적화되며 이 중 sum는 모든 물품의 총 수량이다.
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 101
#define maxV 100005
int v[maxn],num[maxn];
int dp[maxV];
inline void zero(int vol,int val,int W)
{
    for(int i=W;i>=vol;--i)
        dp[i]=max(dp[i],dp[i-vol]+val);
}

inline void complet(int vol,int val,int W)
{
    for(int i=vol;i<=W;++i)
        dp[i]=max(dp[i],dp[i-vol]+val);
}

void multi(int vol,int val,int num,int W)
{
    if(vol*num>=W){
        complet(vol,val,W);
        return;
    }
    for(int i=1;i<=num;i<<=1){
        zero(i*vol,i*val,W);
        num-=i;
    }
    if(num) zero(num*vol,num*val,W);
}

int main()
{
    int n,W,i;
    while(scanf("%d%d",&n,&W)!=EOF&&(n+W))
    {
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;++i) scanf("%d",&v[i]);
        for(i=0;i<n;++i) scanf("%d",&num[i]);
        for(i=0;i<n;++i) multi(v[i],v[i],num[i],W);

        int ans=0;
        for(i=1;i<=W;++i)
            if(dp[i]==i) ++ans;
        printf("%d
",ans); } return 0; }

좋은 웹페이지 즐겨찾기