Today, we continue with the solutions to the knapsack problem, focusing on dynamic programming.
I thought of this solution when I remembered a question from a previous software designer exam for the software exam of the National Computer Rank Examination. I was a participant, and the question was something like this: Usually, different types of food have different nutritional values. Customers often need an algorithm to minimize the cost and obtain the highest nutritional value (without repeating food). Now, we are required to obtain the maximum nutritional value with a cost of N yuan.
Analysis: I believe the principle of solving this problem is well known, the knapsack problem. The question in the exam used dynamic programming, which is related to today's topic. Let's take a look at the code below.
The principle of the dynamic programming solution to this problem: Since different food choices will result in different nutritional results, we need to dynamically bind the prices and the total sum of nutritional values. We can establish an associative array, so that each price will produce different results. Then, we can perform a selection based on the sum of nutritional values. If the sum exceeds a certain limit, we exclude it. If the sum is less than the sum of a cheaper food after adding its nutritional value, we also exclude it. This way, we can calculate the maximum nutritional value for each price range, and then output the result for a specific price range.
Regarding the solution array below, since the result we obtain is the maximum nutritional value for a specific price range, we need to determine which foods are included in this list. Therefore, we compare f[i][S] == f[i+1][S], and if they are the same, it means that the nutritional value remains unchanged and no food is added. Otherwise, it means that food i is added, and we output the result.
/*
- Dynamic programming solution to the knapsack problem combined with the nutritional package problem
- author cg
- date 2008 12 26
*/
#include "stdio.h"
#define N 6 /Define the number of foods/
#define S 100 /Maximum nutritional size/
int main() {
int p[N] = {100,22,80,25,10};/Test data representing prices/
int w[N] = {50,30,51,12,5};/Test data representing nutritional values/
int f[ N + 1 ][ N + 1];/Dynamic price-nutrition relationship array/
int result = 0;/The desired result/
int x[ N ] = {0};/Define the solution array/
int i,j;/Define counters/
int temp;
for (j = 0; j < S+1; j++)
f[N][j] = 0;/Initialization/
for (j = w[N]; j <= S; j++)
f[N][j] = p[N];/Initialize the price/
for(i = N-1; i > 1; i--) {
for(j = 0; j < S+1; j++)
f[i][j] = f[i+1][j];
for(j = w[i]; j <= S; j++){
f[i][j] =
f[i+1][j] > f[i+1][j-w[i]] + p[i] ?
f[i+1][j] : f[i+1][j-w[i]] + p[i];/Check if it is the maximum value, otherwise keep it/
}/for/
}/for/
f[1][S] = f[2][S];
if (S >= w[1])
f[1][S] =
f[1][S] > f[2][S-w[1]] + p[1] ?
f[1][S] : f[2][S-w[1]] + p[1];/Process the final result/
temp= f[1][S];
for (i = 1; i < N; i++){/Solution array/
if (f[i][S] == f[i+1][S])
x[i] = 0;
else {
x[i] = 1;
temp-= w[i];/Subtract the added nutritional value/
}/else/
}/for/
x[N] = f[N][S] ? 1 : 0;
result = f[1][S];
printf("best is %dn", result);/Output the maximum result/
for (i = 1; i <= N ; i++) {/Output the results one by one/
if (x[i] == 1) {
printf(" the p: %d", p[i]);
printf(" the w: %dn", w[i]);
}/if/
}/for/
system("pause");
return 0;
}