The KnapSach Problem
Knapsack
The Knapsack Problem explores the scenario of maximizing the total value of items that can be placed in a knapsack, considering the capacity limitation of the knapsack. This problem is analogous to a scenario where a person, like Bart planning to run away from home, wants to pack the most satisfying foods in his backpack or a thief aiming to fill his bag with the most valuable items while keeping the weight manageable.
The Knapsack problem is one of the most famous NP-Hard problems, indicating that there is no known algorithm that can solve all instances of the problem efficiently for large input sizes. There are several approaches to tackle this problem in programming, especially using C or C++ languages. These include:
1. **Recursive Solution**: This approach explores all possible combinations of items to find the one that maximizes value without exceeding the knapsack's capacity. While it ensures finding the optimal solution, it's computationally expensive and impractical for large numbers of items due to its exponential time complexity.
2. **Dynamic Programming (DP) Solution**: This method is more efficient than the recursive approach. It solves the problem by breaking it down into simpler subproblems and storing the results of these subproblems to avoid computing the same thing multiple times. This technique, known as memoization when applied top-down, or tabulation when applied bottom-up, significantly reduces the computational complexity, making it feasible to solve larger instances of the problem. The DP approach guarantees the accuracy of the results and is faster than the recursive solution.
In the context given, where Bart seeks to pack the most satisfying foods, or a thief aims to select the most valuable items for his bag, dynamic programming would provide a reliable and efficient way to determine the best combination of items to take within the capacity limit. This method balances the trade-off between the total value and the total weight (or volume) of the items chosen to ensure the best outcome.
Solution of Knapsack Problem with Dynamic Algorithm
/*
Soru: Knapsack Dinamik
Proglamlama Dili: C
*/
#include<stdio.h> // Kullanılan kütüphaneler
#include<stdlib.h>
#include<limits.h>
FILE *r,*w;
int dino[1000001];
int canta,nesne,max=INT_MIN; // "canta" değişkeni çantanın kapasitesini tuttuğumuz değiskendir. "nesne" değiskeni girilecek nesne sayısını tuttuğumuz degiskendir. "max" değiskeni ise çantaya alabileceğimiz esyaların değeri en fazla olanı bulmak için tuttuğumuz değiskendir.
void coz(int hacim , int paha) // Bu fonksiyon soruyu çözen fonksiyondur.
{
int i;
if(dino[hacim]<paha)
dino[hacim]=paha;
for(i=1;i<=(canta-hacim);i++)
{
if(dino[i])
{
if(dino[hacim+i]<(dino[i]+paha))
{
dino[hacim+i]=(dino[i]+paha);
if(dino[hacim+i]>max)
max=dino[hacim+i];
}
}
}
}
void oku() // oku() fonksiyonunda okuyacağımız dosyayı açıp "canta" , "nesne" ve nesnelerin "hacim" , "paha" değerlerini okuyup coz(a,b) fonksiyonuna gönderiyoruz.
{
int i,a,b;
r=fopen("in.txt","r");
fscanf(r," %d %d ",&canta,&nesne);
for(i=1;i<=nesne;i++)
{
fscanf(r," %d %d ",&a,&b);
coz(a,b);
}
fclose(r);
}
void yaz() // yaz() fonksiyonunda soruda istenen doğru cevap olarak "max" değerini yazdırıyoruz.
{
w=fopen("out.txt","w");
fprintf(w," %d\n",max);
fclose(w);
}
int main() // main() fonksiyonunda oku() ve yaz() fonksiyonlarini çalıstırır.
{
oku();
yaz();
return 0;
}
Yukarıdaki program kodlarının soruyu çözme süresi.
The reason why the system time is shorter than other times is that reading and writing operations are also included in the other times.
Solution Algorithm of the Problem Using Dynamic Programming Method
When solving the problem, an array as large as the capacity of the bag is taken. Each object read is processed in this array. All elements of the array are zero. Since each element in the array determines the maximum value at that capacity, it is necessary to place the maximum values when placing an element at that index in the array. While doing this, if the value of the object is larger than the value written at its size location, it is written there, and the array is scanned from beginning to end. If there is a non-zero element in the array, go to the place where the index of that element plus the value of the object read is found. If the value written there is less than the sum of the object's value and the value written at the index where it came from, this total is written there.
in.txt
7
3
2 3
3 5
4 5
If we apply the algorithm for the example input;
First, we take the object with a volume of 2 and a value of 3.
We assign the object's value to the array's index 2 (Which is 3). When we look at the array from the beginning, we see that the first filled element is at index number 2. We go to index number 4 by adding 2+2, and assign the value of 6 by adding 3+3. When we perform this operation for the entire array, the array takes the following form.
When we take the second object, which has a volume of 3 and a value of 5, we assign a value of 5 to index number 3. Scanning the array from the beginning, we again see that the first filled element is at index number 2. We go to index number 5 by adding 2+3 and assign a value of 8 by adding 3+5. When we apply this process to the entire array, the array takes the following form.
The other object does not cause any change in the array. The answer to the problem becomes the largest of the array elements.
The processing logic of the algorithm is as follows; after placing the first element, when moving to index number 4 by calculating 2+2, we assume that we have placed two objects of volume 2 in the bag. Similarly, when moving to index number 5 by calculating 2+3, we assume that we have taken one object of volume 2 and one object of volume 3. Since we try all objects in this manner, the largest number in the array at the end becomes the answer to our question.
Leveraging NP-Complete Problems in Restaurant Orders.
Chotchkies Restaurant
Appetizers:
-Fruit Salad $ 2.15
-French Fries $ 2.75
-Salad $ 3.35
-Chicken Wings $ 3.55
-Mozzarella Cheese Bread $ 4.20
-Sampler Plate
Sandwiches:
-Barbecue $ 6.55
Conversation:
Customer: We want appetizers totaling exactly $15.05.
Waiter: Exactly?..
Customer: This Knapsack problem on the paper might help you.
Waiter: Listen, I need to check on six more tables...
Customer: Of course, in the fastest way possible. Would you like some help from the Traveling Salesman problem?