Path: utzoo!attcan!uunet!mcsun!ukc!reading!minster!mike
From: mike@minster.york.ac.uk
Newsgroups: comp.theory
Subject: An NP-Complete Problem?
Message-ID: <637950193.627@minster.york.ac.uk>
Date: 20 Mar 90 16:23:13 GMT
Organization: Department of Computer Science, University of York, England
Lines: 14


Is the following problem NP-something?

Given a get of tuples (bi, ci) and a value d, where
the bi and ci are zero or positive integers, and d
a non-zero positive integer, is it possible to test
for the existance of a subset such that

sum bi <= d <= sum bi + sum ci

Any suggestions appreciated

mike@minster.york.ac.uk
Mike Richardson