0-1背包问题matlab代码
时间: 2023-08-01 18:12:40 浏览: 51
Sure! Here's an example of a MATLAB code for solving the 0-1 Knapsack problem:
```matlab
function [maxValue, selectedItems] = knapsack(values, weights, capacity)
n = length(values);
dp = zeros(n+1, capacity+1);
keep = zeros(n, capacity+1);
for i = 1:n
for w = 1:capacity+1
if weights(i) <= w && values(i) + dp(i, w-weights(i)) > dp(i, w)
dp(i+1, w) = values(i) + dp(i, w-weights(i));
keep(i, w) = 1;
else
dp(i+1, w) = dp(i, w);
end
end
end
maxValue = dp(n+1, capacity);
selectedItems = findSelectedItems(keep, weights);
function selected = findSelectedItems(keep, weights)
i = size(keep, 1);
w = size(keep, 2);
selected = [];
while i >= 1 && w >= 1
if keep(i, w) == 1
selected = [selected, i];
w = w - weights(i);
end
i = i - 1;
end
end
end
```
To use this code, you can define your values and weights arrays and call the `knapsack` function with these arrays and the capacity of the knapsack. The function will return the maximum value that can be achieved and the indices of the selected items.
Here's an example usage:
```matlab
values = [60, 100, 120];
weights = [10, 20, 30];
capacity = 50;
[maxValue, selectedItems] = knapsack(values, weights, capacity);
disp("Maximum value: " + maxValue);
disp("Selected items: " + num2str(selectedItems));
```
This code will solve the 0-1 Knapsack problem for the given values, weights, and capacity, and display the maximum value and the indices of the selected items.