Form of the knapsack problem

Assignment Help Basic Computer Science

Reference no: EM13968347

1. One form of the knapsack problem is as follows: We are given a set of integers, A = a1, a2, ... , aN, and an integer, K. Is there a subset of A whose sum is exactly K?

a. Give an algorithm that solves the knapsack problem in O(NK) time.

b. Why does this not show that P = NP?

2. You are given a currency system with coins of (decreasing) value c1, c2, ... , cN cents.

a. Give an algorithm that computes the minimum number of coins required to give K cents in change.

b. Give an algorithm that computes the number of different ways to give K cents in change.

Reference no: EM13968347

Questions Cloud

List two different ways to improve accuracy or circumvent : What are the two most common causes for people not being able to reconcile their bank statements accurately?

What is the speed of the electrons emitted by this device : Electrons produced by a certain device are observed to travel in a circular path with a radius of 4.4 cm when placed in a uniform magnetic field whose strength is 47 MN/C. What is the speed of the electrons emitted by this device?

Nonattacking queens on the board : In the game of chess, a knight in row R and column C may move to row 1 ≤ Rt ≤ B and column 1 ≤ Ct ≤ B (where B is the size of the board) provided that either

Complete project by creating unique lesson on major concept : Complete the project by creating a unique lesson on a major concept/event of the 1970s. Incorporate maps, images, and video from MySearchLab and from outside sources.

Form of the knapsack problem : One form of the knapsack problem is as follows: We are given a set of integers, A = a1, a2, ... , aN, and an integer, K. Is there a subset of A whose sum is exactly K?

Describe the basic features of the investment as foundation : In this section, discuss the incremental impact of a hypothetical, but reasonable, simple new investment project, such as a new product or facility or a cost-cutting investment, as an initial step in thinking about the future. Be sure to address t..

?nd the ?rst occurrence : The pattern-matching problem is as follows: Given a string, S, of text, and a pat- tern, P, ?nd the ?rst occurrence of P in S. Approximate pattern matching allows k mismatches of three types:

Write a summary of four different media technologies : Write a summary of four different media technologies (for example, print, telegraph, telephone, radio, television, Internet, and so on) and also post the summaries in your Blog (four summaries total)

Which conflict resolution techniques you would use : Analyze which conflict resolution techniques you would use. Submit your response to your instructor through the online course and add it to your Blog

User Account

All Pages