흑과학기술: 다중 가방 최적화

4710 단어

흑과학기술의: 다중 가방 최적화
최적화 방법 1: 바이너리 최적화
사상: v[i]개 물품을 1, 2, 4,...2^k, 나머지, 그리고 01 가방
코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>
#include 
#include 
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define frep(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
struct bag
{
    int v;
    int w;
};
const int N=10000005;
int n;
ll t;
ll val[N],w[N];
int cnt=0;
bag a[N];
ll f[N];
ll ans=0;
int main()
{
    scanf("%d%lld",&n,&t);
    rep(i,1,n)
    {
        ll W;
        scanf("%lld%lld%lld",&val[i],&w[i],&W);
        for(ll j=1;j<=W;j<<=1)
        {
            cnt++;
            a[cnt].v=val[i]*j;
            a[cnt].w=w[i]*j;
            W-=j;
        }
        if(W)
        {
            cnt++;
            a[cnt].v=val[i]*W;
            a[cnt].w=w[i]*W;
        }
    }
    n=cnt;
    rep(i,1,n)
    {
        frep(j,t,a[i].w)
        {
            f[j]=max(f[j],f[j-a[i].w]+a[i].v);
        }
    }
    rep(i,0,t) ans=max(ans,f[i]);
    printf("%lld
",ans);
    return 0;
}

최적화 방법2: 단조로운 대기열 최적화
할 줄 모르다
최적화 방법 3: 신기한 최적화
같은 종류에 출현 횟수>2의 수
두 개를 합쳐서.
끝까지 병합, 끝
예:

P3563 [POI2013]POL-Polarization

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다