hdu 2844 coins(다중 가방 + 바이너리 최적화)
예제 2 설명:
2 5
1 4 2 1전형적인 다중 가방 문제.
이곳의 액면가는 가방 문제 중의 물품의 부피와 물품의 가치에 해당한다.
따라서 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
