01背包问题代码实现

01背包问题

问题描述： 给定一组物品，每个物品有一个重量和一个价值，另有一个背包，它的容量为限定的重量。目标是找出一个物品的子集，使得这些物品的总重量不超过背包的容量，并且它们的总价值最大。

动态规划解法

1. 状态定义：

   • 用 dp[i][w] 表示前 i 个物品中可以放入一个容量为 w 的背包的最大价值。

2. 状态转移方程：

   • 如果不选择第 i 个物品：dp[i][w] = dp[i-1][w]
   • 如果选择第 i 个物品：dp[i][w] = dp[i-1][w-weight[i-1]] + value[i-1]
   • 综合两种情况：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1])

3. 初始化：

   • 当没有物品或容量为0时，dp[0][w] = 0 和 dp[i][0] = 0

4. 结果：

   • 最终结果在 dp[n][W]，其中 n 是物品的数量，W 是背包的容量。

C实现

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int f[5][9]={0};
int w[5] = {0,2,3,4,5};
int v[5] = {0,3,4,5,8};
int main()
{
    int i,j;
    memset(f,0,sizeof(f));
    for(int i=1;i<5;i++)
    {
        for(int j=1;j<9;j++)
        {
            if(w[i]>j)
            f[i][j]=f[i-1][j];
            else 
            f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
        }
    }
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<9;j++)
        {
            printf("f[%d][%d]=%d\n",i,j,f[i][j]);
        }
    
    }
    return 0;
}

C++实现

#include <iostream>
#include <vector>
using namespace std;

int knapsack(int W, const vector<int> &wt, const vector<int> &val) {
    int n = val.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (wt[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    vector<int> val = {60, 100, 120};
    vector<int> wt = {10, 20, 30};
    int W = 50;
    cout << "最大价值: " << knapsack(W, wt, val) << endl;
    return 0;
}

Python实现

def knapsack(W, wt, val):
    n = len(val)
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][W]

# 示例用法
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
print(f"最大价值: {knapsack(W, wt, val)}")

解释

1. 状态定义：

   • dp[i][w] 表示前 i 个物品中可以放入容量为 w 的背包的最大价值。

2. 状态转移方程：

   • 如果不选择第 i 个物品：dp[i][w] = dp[i-1][w]
   • 如果选择第 i 个物品：dp[i][w] = dp[i-1][w-weight[i-1]] + value[i-1]
   • 综合两种情况：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1])

3. 初始化：

   • dp[0][w] = 0 和 dp[i][0] = 0 表示当没有物品或容量为0时，最大价值为0。

4. 计算结果：

   • 通过迭代填充 dp 数组，最终结果存储在 dp[n][W] 中，其中 n 是物品的数量，W 是背包的容量。