Is it possible to easily check if an instance of the 0-1 knapsack problem is unsolvable? Example: Assign 10 40-min tasks to 8 employees that have 60 minutes available each. Clearly, this instance is unsolvable as a 0-1 knapsack problem (but solvable as a fractional knapsack problem). I don't want to solve the 01-knapsack problem, but just detect if it is NOT solvable. Thanks in advance!
EDITED PROBLEM 1 - THOROUGH PROBLEM DESCRIPTION
Below is a more thorough problem description.
I have a set of tasks with a given duration and a given time window each task has to be performed within (e.g the task duration for a given task could be 20 minutes and it has to be performed in the time interval 08:00-09:00). In addition, each task has a required skill, meaning that the employee carrying out the task needs to have a certain competence level (e.g tasks with required skill equal to 2 can only be carried out by employees with a competence level greater than or equal to 2).
I have a set of employees that work shifts. E.g an employee work from 08:00 to 13:00. Each employee has a given competence level, described above. The tasks are supposed to be allocated to the employees, and an employee cannot perform more than one task at the same time. E.g the same employee cannot perform BOTH task 1 (duration 10 minutes and time window 08:10-08:20) and task 2 (duration 30 minutes and time window 08:10-08:45). In addition, there are some tasks that a given employee cannot perform due to other reasons.
I want to check (preferably in polynomial time) a given problem instance (with tasks and employees) is not solvable, meaning that there exists some conflict such that it is impossible to allocate all tasks (see example above in original question formulation). To my understanding, it is NP-hard to solve the problem, but I just want to prove/detect that a given instance is unsolvable. Is it possible to easily check if there does not exist a possible assignment of tasks to employees?
EDIT 2 - BETTER DEFINITION OF THE GOAL
To be clear, I don't want an algorithm that ALLWAYS finds out if an instance is unsolvable or not. I am just looking for a way (an algorithm) that as OFTEN AS POSSIBLE finds out if the instance is unsolvable, and if the algorithm is uncertain (some efficient test did not detect that the instance was unsolvable) then I am fine with the problem instance being either solvable or unsolvable. So the algorithm I am looking for should detect as many "unsolvable instances" as possible, but not all.
Thanks in advance for your answers and contributions!