Python 욕심 알고리즘 기반 가방 문제 해결 예시
탐욕 알고리즘(일명 탐욕 알고리즘)은 문 제 를 풀 때 항상 현재 로 서 는 가장 좋 은 선택 을 하 는 것 을 말한다.즉,전체적으로 가장 좋 은 것 을 고려 하지 않 고 그 가 한 것 은 특정한 의미 에서 부분 적 으로 가장 좋 은 것 이다.
욕심 산법 은 모든 문제 에 대해 전체적인 최 적 화 를 얻 을 수 있 는 것 이 아니 라 관건 은 욕심 전략의 선택 이다.선택 한 욕심 전략 은 반드시 비효 율 성 을 가 져 야 한다.즉,특정한 상태 이전의 과정 은 이후 의 상태 에 영향 을 주지 않 고 현재 상태 와 만 관련 이 있다.
완전 가방 문제:주어진 n 개 아 이 템 과 1 개 용량 C 의 가방,아 이 템 i 의 무 게 는 Wi,그 가 치 는 Vi,가방 문 제 는 가방 에 들 어 가 는 아 이 템 을 어떻게 선택 하 느 냐 에 따라 가방 에 들 어 가 는 아 이 템 의 총 가치 가 가장 큽 니 다.0-1 가방 과 는 완전 가방 문제 중 일 부 를 가방 에 넣 을 수 있 으 나 중복 으로 넣 을 수 없습니다.
디자인 알고리즘 의 사고방식 은 매우 간단 하 다.물품 의 단위 가 치 를 계산 한 다음 에 가능 한 한 단위 중량 가치 가 높 은 물품 을 가방 에 넣는다.
python 구현 코드 는 다음 과 같 습 니 다:
# coding=gbk
# ，
import time
__author__ = 'ice'
class goods:
def __init__(self, goods_id, weight=0, value=0):
self.id = goods_id
self.weight = weight
self.value = value
# 0-1
def knapsack(capacity=0, goods_set=[]):
#
goods_set.sort(key=lambda obj: obj.value / obj.weight, reverse=True)
result = []
for a_goods in goods_set:
if capacity < a_goods.weight:
break
result.append(a_goods)
capacity -= a_goods.weight
if len(result) < len(goods_set) and capacity != 0:
result.append(goods(a_goods.id, capacity, a_goods.value * capacity / a_goods.weight))
return result
some_goods = [goods(0, 2, 4), goods(1, 8, 6), goods(2, 5, 3), goods(3, 2, 8), goods(4, 1, 2)]
start_time = time.clock()
res = knapsack(6, some_goods)
end_time = time.clock()
print(' ：' + str(end_time - start_time))
for obj in res:
print(' :' + str(obj.id) + ' , :' + str(obj.weight) + ', :' + str(obj.value), end=',')
print(' :' + str(obj.value / obj.weight))
# ：2.2807240614677942e-05
# :3 , :2, :8, :4.0
# :0 , :2, :4, :2.0
# :4 , :1, :2, :2.0
# :1 , :1, :0.75, :0.75
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Python의 None과 NULL의 차이점 상세 정보그래서 대상 = 속성 + 방법 (사실 방법도 하나의 속성, 데이터 속성과 구별되는 호출 가능한 속성 같은 속성과 방법을 가진 대상을 클래스, 즉 Classl로 분류할 수 있다.클래스는 하나의 청사진과 같아서 하나의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
