Basic introduction to C language for beginners, looking at some common examples to learn some coding ideas. Please be gentle with the feedback.
Dynamic Programming – 0-1 Knapsack Problem
Problem Overview: Given items and a knapsack with a capacity of , each item has a weight and a value , the goal is to select several items to put into the knapsack such that the total value of the items in the knapsack is maximized while the total weight does not exceed the knapsack’s capacity.
In the above example, since each item has only two possible states (taken or not taken), corresponding to 0 and 1 in binary, this type of problem is called the “0-1 Knapsack Problem”.
Explanation
In the example, the known conditions include the weight of the th item, its value , and the total capacity of the knapsack .
Let the DP state represent the maximum total value that can be achieved with a knapsack of capacity when only the first items can be placed.
Consider the state transition. Assume that all states of the first items have been processed. For the th item, when it is not placed in the knapsack, the remaining capacity of the knapsack remains unchanged, and the total value of the items in the knapsack also remains unchanged, so the maximum value in this case is ; when it is placed in the knapsack, the remaining capacity of the knapsack will decrease, and the total value of the items in the knapsack will increase , so the maximum value in this case is.
From this, we can derive the state transition equation:
If a two-dimensional array is used directly to record the states, it may lead to MLE. We can consider using a rolling array to optimize.
Since only affects , we can eliminate the first dimension and directly use to represent the maximum value when the knapsack capacity is at the current item, leading to the following equation:
Summary of State Transition Equations (Key)
For each item and capacity:
Case 1: Do not select the item → Value equals the maximum value of the first items under capacity j → Case 2: Select the th item (must satisfy) → Value = value of the th item + maximum value of the first items under the remaining capacity → Optimal decision: Take the maximum value of the two cases
#include <iostream>
using namespace std;
constexpr int MAXN = 13010;
// Define a constant `MAXN` with a value of 13010. `constexpr` indicates that this is a compile-time constant used to specify the size of the array. It represents the maximum possible number of items or knapsack capacity, set to 13010 based on problem constraints.
int n ,W , w[MAXN],v[MAXN],f[MAXN];
//n: number of items
//w: maximum capacity of the knapsack
//w[MAXN] array: stores the weight of each item
//v[MAXN] array: stores the value of each item
//f[MAXN] array: dynamic programming state storage, maximum value obtainable with knapsack capacity i
int main() {
// Read input data
cin >> n >> W; // Input number of items n and knapsack capacity W
for (int i = 1; i <= n; i++)
cin >> w[i] >> v[i]; // Loop to read each item's weight w[i] and value v[i] (index starts from 1)
// Core dynamic programming process (0-1 knapsack one-dimensional array optimization)
for (int i = 1; i <= n; i++) { // Outer loop: iterate through each item (from the 1st to the nth)
for (int l = W; l >= w[i]; l--) { // Inner loop: traverse knapsack capacity in reverse (from W to current item weight w[i])
// State transition equation: decision whether to place item i in the knapsack
if (f[l - w[i]] + v[i] > f[l]) { // If using item i results in a greater value
f[l] = f[l - w[i]] + v[i]; // Update f[l]: include item i (weight w[i], value v[i])
} // Otherwise, keep f[l] unchanged (do not include item i)
}
}
// Output result
cout << f[W]; // Output f[W]: maximum value that can be carried in a knapsack of capacity W
return 0; // Program ends normally
}AI provided a code (many things I don’t know)
#include <stdio.h>
#include <stdlib.h>
// Auxiliary function: returns the larger of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
int main() {
int n, C; // n: number of items, C: knapsack capacity
// User input
printf("=== 0-1 Knapsack Problem Solver ===\n");
printf("Input number of items: ");
scanf("%d", &n);
printf("Input knapsack capacity: ");
scanf("%d", &C);
// Dynamically allocate memory
int *weights = (int *)malloc(n * sizeof(int)); // Item weights
int *values = (int *)malloc(n * sizeof(int)); // Item values
// Input item information
printf("\nInput the weight and value of each item:\n");
for (int i = 0; i < n; i++) {
printf("Item %d (Weight Value): ", i + 1);
scanf("%d %d", &weights[i], &values[i]);
}
// =================================
// Core algorithm: Dynamic Programming
// =================================
// 1. Create DP table (two-dimensional array)
int **dp = (int **)malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = (int *)malloc((C + 1) * sizeof(int));
}
// 2. Initialize boundary conditions
// No items, value = 0
for (int j = 0; j <= C; j++) {
dp[0][j] = 0;
}
// Knapsack capacity = 0, value = 0
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
// 3. Fill DP table
for (int i = 1; i <= n; i++) { // Iterate through each item
for (int j = 1; j <= C; j++) { // Iterate through each knapsack capacity
int current_weight = weights[i-1];
int current_value = values[i-1];
if (current_weight <= j) {
// Can choose the current item: take the maximum of "choose" and "not choose"
dp[i][j] = max(
dp[i-1][j], // Do not choose the current item
current_value + dp[i-1][j - current_weight] // Choose the current item
);
} else {
// Current item is too heavy, cannot choose
dp[i][j] = dp[i-1][j];
}
}
}
// Output maximum value
printf("\nMaximum Value: %d\n", dp[n][C]);
// =================================
// Backtrack: find the specific items chosen
// =================================
printf("Chosen items: ");
int remaining_capacity = C;
for (int i = n; i >= 1; i--) {
// If dp[i][j] > dp[i-1][j], it means item i was chosen
if (dp[i][remaining_capacity] != dp[i-1][remaining_capacity]) {
printf("%d ", i); // Output item number
remaining_capacity -= weights[i-1]; // Subtract item weight
}
}
printf("\n");
// =================================
// Visualize DP table (optional)
// =================================
printf("\nDP Table:\n");
printf(" ");
for (int j = 0; j <= C; j++) printf("%2d ", j);
printf("\n");
printf(" ");
for (int j = 0; j <= C; j++) printf("---");
printf("\n");
for (int i = 0; i <= n; i++) {
printf("%2d | ", i);
for (int j = 0; j <= C; j++) {
printf("%2d ", dp[i][j]);
}
printf("\n");
}
// Free memory
free(weights);
free(values);
for (int i = 0; i <= n; i++) free(dp[i]);
free(dp);
return 0;
}