2011•Advanced materials researchRequires access

Solving 0-1 Knapsack Problems by Greedy Method and Dynamic Programming Method

Lu Liu

Abstract

The 0-1 knapsack problem is typical problem in computer science and its solution is a hot spot in algorithms design and verification. Because it is very hard to solve, it is very important in the research on cryptosystem and number theory. In this paper, the 0-1 knapsack problem and its algorithm is analyzed firstly. And then this paper presents two kinds of expand form, and proposes two efficient algorithms based on dynamic programming and greedy algorithm to solve the proposed problems. Simulation results show it is effective.

About this research paper

What this paper is about

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Key concepts: Knapsack problem, Greedy algorithm, Continuous knapsack problem, Mathematical optimization, Change-making problem, Dynamic programming, Computer science, Generalized assignment problem