검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Open Access
Online Removable Knapsack Problem for Integer-Sized Unweighted Items
오픈 액세스
정수 크기의 비가중 항목에 대한 온라인 제거 가능 배낭 문제

Hiroshi FUJIWARA, Kanaho HANJI, Hiroaki YAMAMOTO

  • 조회수

    135

  • 이것을 인용
  • Free PDF (1.6MB)

요약 :

온라인 이동식 배낭 문제에서는 각각의 가치와 크기가 표시된 일련의 항목이 하나씩 주어집니다. 아이템이 도착할 때마다 플레이어는 해당 아이템을 배낭에 넣을지 아니면 버릴지를 결정해야 합니다. 플레이어는 이미 배낭에 들어 있는 일부 항목을 버릴 수도 있습니다. 목표는 배낭의 총 가치를 극대화하는 것입니다. Iwama와 Taketomi는 각 항목의 값이 해당 크기와 같은 경우에 대한 최적의 알고리즘을 제공했습니다. 본 논문에서는 배낭의 용량이 양의 정수라는 추가적인 제약 조건이 있는 경우를 고려합니다. N 항목의 크기는 모두 필수입니다. 각 양의 정수에 대해 N, 우리는 알고리즘을 설계하고 최적성을 증명합니다. 경쟁률은 단조롭지 않은 것으로 나타났습니다. N.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.9 pp.1195-1202
발행일
2022/09/01
공개일
2022/03/08
온라인 ISSN
1745-1337
DOI
10.1587/transfun.2021DMP0013
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주
알고리즘 및 데이터 구조

작성자

Hiroshi FUJIWARA
  Shinshu University
Kanaho HANJI
  Shinshu University
Hiroaki YAMAMOTO
  Shinshu University

키워드