Một cái ba lô là một cái túi. Và bài toán cái ba lô giải quyết việc xếp đồ vào túi dựa trên giá trị của đồ. Mục đích là để tối đa hóa giá trị bên trong chiếc túi. Trong Knapsack 0-1, bạn có thể đặt hoặc loại bỏ mục đó, không có khái niệm đặt một số phần của mục vào túi.
Bài toán mẫu
Value of items = {20, 25,40}
Weights of items = {25, 20, 30}
Capacity of the bag = 50 Phân bổ trọng lượng
25,20{1,2}
20,30 {2,3}
If we use {1,3} the weight will be above the max allowed value.
For {1,2} : weight= 20+25=45 Value = 20+25 = 45
For {2,3}: weight=20+30=50 Value = 25+40=65 Giá trị lớn nhất là 65 nên chúng tôi sẽ đặt mục 2 và 3 vào túi đựng.
CHƯƠNG TRÌNH CHO BÀI TOÁN KNAPSACK 0-1
#include<stdio.h>
int max(int a, int b) {
if(a>b){
return a;
} else {
return b;
}
}
int knapsack(int W, int wt[], int val[], int n) {
int i, w;
int knap[n+1][W+1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i==0 || w==0)
knap[i][w] = 0;
else if (wt[i-1] <= w)
knap[i][w] = max(val[i-1] + knap[i-1][w-wt[i-1]], knap[i-1][w]);
else
knap[i][w] = knap[i-1][w];
}
}
return knap[n][W];
}
int main() {
int val[] = {20, 25, 40};
int wt[] = {25, 20, 30};
int W = 50;
int n = sizeof(val)/sizeof(val[0]);
printf("The solution is : %d", knapsack(W, wt, val, n));
return 0;
} Đầu ra
The solution is : 65