Python，回溯法求解0-1背包，bug求解答

Question

关于0-1背包递归回溯求解的过程
我使用的是vscode上的Python插件，借助flask框架搭了一下前端界面
思路如下：
最初给四个参数，分别是i：当前最大物品编号，current_weight：当前重量；current_value：当前价值；current_solution：当前解（向量）
之后首先判断能不能走左支（当前物品能否放进背包），能走则走左支并递归。
如果不能走左支则计算当前的bound右支上界，如果bound大于当前bestp，那么就需要进入右支进行递归，否则可以剪枝处理
但遇到了问题
问题描述如下：
测试样例为：5 15 25 27 30 12 30 44 46 50，前半为重量向量，后半为价值向量。背包容量为50
程序会一直输出86，（1 1 1 0 0）正确解应该是92 （1 1 0 0 1）。具体描述见图片。对应的html网页和源码附上
根据我的理解，可能是在左支出来之后进右支的过程中出现错误，但没有报错没有卡死，而是完成了运行，所以一直也没能找到出现问题的地方。
还请各位帮我看看呗！

#输入是一个数组，一个数，传递回来的处理是，数组先拆成俩存起来，然后原数组再和数凑成一个长数组，这是输入纸带的内容，固定
#工作纸带输出：当前重量，当前价值，当前解决方案
#输出纸带更新最优解和最优解的解决方案
#栈中展示层级
#列表内容：重量，价值，0-1向量，最优值，最优向量，层级
from flask import Flask, jsonify, render_template, request
app = Flask(__name__, template_folder='templates')
class KRB:
    def __init__(self):
        self.tape1_list = []
        self.result = 0  
        self.inputarray=[]      
        self.capacity = 0
        self.curweight = 0
        self.curvalue = 0
        self.cursolution = []
        self.bestvalue = 0
        self.bestsolution = []
        self.inputweight = []
        self.inputvalue = []
        self.depth = 0
        self.stack = []
        self.list = []
        self.data_store={'list':[],'len':0}
        self.depthstack = []
        self.r = 0
        self.cp = 0
        self.bestp = 0
        self.bound = 0


    def clear(self):
        self.tape1_list = []
        self.result = 0  
        self.inputarray=[]      
        self.capacity = 0
        self.curweight = 0
        self.curvalue = 0
        self.cursolution = []
        self.bestvalue = 0
        self.bestsolution = []
        self.inputweight = []
        self.inputvalue = []
        self.depth = 0
        self.list = []
        self.depthstack = []
        self.r = 0
        self.cp = 0
        self.bestp = 0
        self.bound = 0


    def show(self):
        string1 = ""
        for i in self.tape1_list:
            string1 += f"{i}"
            string1 += " "
        string2 = ""
        string3 = ""
        string2 = f"{self.curweight} {self.curvalue} {self.cursolution}"
        string3 = f"{self.bestvalue} {self.bestsolution}"
        string5 = ""
        string5 += f"{self.depthstack}"
        string1 = string1.replace("[", "").replace("]", "")
        string2 = string2.replace("[", "").replace("]", "")
        string3 = string3.replace("[", "").replace("]", "")
        string5 = string5.replace("[", "").replace("]", "")    
        self.list.append([string1,string2,string3,string5])
        


    def get_input(self,numbers,key):
        string_list = numbers.split()
        self.capacity = int(key)
        self.tape1_list = [int(num) for num in string_list] + [self.capacity]
        n=len(string_list)//2
        self.inputweight = string_list[:n]
        self.inputvalue = string_list[n:]        
        self.show()


    
        


    def knapsack_backtracking(self):
        n = len(self.inputweight)
        self.bestvalue = 0
        max_value = 0
        best_solution = []
        self.bestsolution=[]
        current_solution = []
        for i in range(n):
            best_solution.append(0)
            current_solution.append(0)
            self.bestsolution.append(0)
        self.depth=0
        self.show()
        self.depthstack = []

        def backtrack(i, current_weight, current_value, current_solution):
            nonlocal max_value,best_solution
            # 记录当前状态
            #print(i, current_weight, current_value, current_solution,max_value,best_solution, self.depthstack)
            #print("\n")
            self.depthstack.append(self.depth)
            self.curweight = current_weight
            self.curvalue = current_value
            self.cursolution = current_solution
            #self.bestvalue = max_value
            #self.bestsolution = best_solution
            #self.stack.append((i, current_weight, current_value, current_solution,max_value,best_solution, self.depthstack))
            self.show()

            if self.curvalue > self.bestvalue:        
                self.bestvalue = self.curvalue
                list_try=self.cursolution[:]
                self.bestsolution = list_try  
            
            if i<n:

                #首先判定能不能走左支
                if self.capacity - current_weight>=int(self.inputweight[i]):
                    #走左支                          
                    current_solution[i]=1
                    self.depth+=1
                    backtrack(i+1,current_weight+int(self.inputweight[i]),current_value+int(self.inputvalue[i]),current_solution)
                    self.depth-=1
                    self.depthstack.pop()

                    
                    

                #走完左支的情况下算一下右支上界，如果上界大于当前最优值，走右支，否则回溯
                
                #计算右支上界
                def bound(i):
                    leftw=self.capacity-self.curweight
                    b=self.curvalue
                    while i<=n and self.inputweight[i]<=leftw:
                        leftw-=self.inputweight[i]
                        b+=self.inputvalue[i]
                        i=i+1
                    if i<=n:
                        b+=self.inputvalue[i]/self.inputweight[i]*leftw
                        return b
                b=bound(i)    
                if b>self.bestvalue:
                    current_solution[i]=0
                    self.depth+=1
                    backtrack(i+1,current_weight,current_value,current_solution)
                    self.depth-=1
                    self.depthstack.pop()
                    return
                    
                if b<=self.bestvalue:
                    return
            if i==n:
                return          
        # 从第0个物品开始进行回溯
        backtrack(0, 0, 0, current_solution)
        print(len(self.list))
        return max_value, best_solution

以上是Python代码

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>递归回溯实现0-1背包</title>
    <style>
        body {
            font-family: Arial, sans-serif;
            margin: 20px;
            background-color: #f6e8c2;
            /*display:flex;*/
            justify-content:center;
            /*text-align: center;*/ 
            
            
        }
        .container {
            margin: auto;
            padding: 20px;
            border: 1px solid #ccc;
            border-radius: 5px;
            background-color: #fff;
            width: 85%;
            height: 90%;
            box-shadow: 0 0 10px rgba(0, 0, 0, 0.1);
            display: flex;
        }
        .left-panel, .right-panel {
            flex: 1;
            padding: 20px;
        }
        h1 {
            text-align: center;
            margin-bottom: 20px;
        }
        .input-group {
            margin-bottom: 15px;
        }
        label {
            font-weight: bold;
        }
        input[type="text"] {
            width: 100%;
            padding: 8px;
            font-size: 16px;
            border: 1px solid #ccc;
            border-radius: 4px;
            box-sizing: border-box;
        }
        .output {
            width: 100%;
            height: 100px;
            border: 2px solid #1a1919;
            border-radius: 5px;
            padding: 10px;
            box-sizing: border-box;
            margin-bottom: 20px;
            margin-top: 20px;
            overflow-y: auto;
            
        }
        .output2 {
            width: 100%;
            height: 100px;
            border: 2px solid #1a1919;
            border-radius: 5px;
            padding: 10px;
            box-sizing: border-box;
            margin-bottom: 20px;
            margin-top: 20px;
            overflow-y: auto;
            
        }
        .output3 {
            width: 100%;
            height: 100px;
            border: 2px solid #1a1919;
            border-radius: 5px;
            padding: 10px;
            box-sizing: border-box;
            margin-bottom: 20px;
            margin-top: 20px;
            overflow-y: auto;
        }
        .output-label {
            font-weight: bold;
            margin-bottom: 5px;
        }
        .status {
            border: 1px solid #ccc;
            padding: 10px;
            min-height: 50px;
            overflow-wrap: break-word;
            margin-bottom: 10px;
        }
        .status-label {
            font-weight: bold;
            margin-bottom: 5px;
        }
        .btn-group {
            text-align: center;
        }
        .btn-group button {
            padding: 10px 20px;
            margin-right: 10px;
            font-size: 16px;
            cursor: pointer;
            border: none;
            border-radius: 4px;
            background-color: #4CAF50;
            color: white;
            transition: background-color 0.3s ease;
        }
        .btn-group button:hover {
            background-color: #45a049;
        }

        .stack-container {
            display: flex;
            flex-direction: column;
            align-items: center;
        }
        .stack {
            width: 350px;
            height: 700px;
            border: 2px solid #333;
            border-radius: 5px;
            display: flex;
            
            overflow: hidden;
        }

        .sidebar {
            height: 100%;
            width: 250px;
            position: fixed;
            top: 0;
            left: -250px;
            background-color: #bfab8e;
            transition: all 0.3s ease;
            text-align: center;
        }
        .sidebar ul {
            list-style: none;
            padding: 0;
            margin: 0;
        }
        .sidebar ul li {
            padding: 15px 20px;
            border-bottom: 1px solid #666;
            color: #fff;
        }
        .sidebar ul li a {
            color: #fff; /* 设置超链接文本颜色为白色 */
            text-decoration: none; /* 去掉超链接的下划线 */
        }
        .sidebar ul li:hover {
            background-color: #555;
        }
        .menu-toggle {
            display: none;
        }

        .menu-toggle:checked + .sidebar {
            left: 0;
        }
        .menu-icon {
            position: fixed;
            top: 50px;
            left: 5px;
            z-index: 2;
            font-size: 24px;
            cursor: pointer;
            color: #fff;
        }

        @media (max-width: 768px) {
            .sidebar {
            left: 0;
            }

            .menu-toggle:checked + .sidebar {
            left: -250px;
            }
        }

        .content {
            margin-left: 250px;
            padding: 20px;
        }
    </style>
</head>
<body>
    <input type="checkbox" class="menu-toggle" id="menu-toggle">
    <div class="sidebar">
    <ul>
        <li><a href="TurLingo">首页</a></li>
        <li><a href="TurlingChoice">图灵机仿真选择</a></li>
        <li><a href="RecurChoice">递归仿真选择</a></li>
        <li><a href="Members">团队信息</a></li>
    </ul>
    </div>
    <label for="menu-toggle" class="menu-icon">&#9776;</label>
    <h1>递归回溯实现0-1背包</h1>
    <div class="container">
        <div class="left-panel">

        <form action="/Knap_Backtrak" method="post">
            <div class="input-group">
                <label for="numbers">输入一串数字（用空格分隔）：</label>
                <input type="text" id="numbers" name="numbers" placeholder="例如：1 3 5 7 9">
            </div>
            <div class="input-group">
                <label for="capacity">输入背包容量：</label>
                <input type="text" id="capacity" name="capacity" placeholder="例如：5">
            </div>
            
            <div class="output3">
                <div class="output-label">输入纸带：</div>
                <div id="output-tape1"></div>
            </div>
            <div class="output2">
                <div class="output-label">工作纸带：</div>
                <div id="output-tape2"></div>
            </div>
            <div class="output">
                <div class="output-label">输出纸带：</div>
                <div id="output-tape3"></div>
            </div>
            <div class="output">
                <div class="output-label">当前状态：</div>
                <div id="status-text"></div>
            </div>
            
            <div class="btn-group">
                <button type="button" id="start-button">开始</button>
                <button type="button" id="next-button">下一步</button>
                <button type="button" id="end-button">结束搜索</button>
            </div>
        </form>
        </div>
        <div class="right-panel">
            <div class="stack-container">
                <div class="stack">
                    <div class="output-label">栈:</div>
                    <div id="stack-text"></div>
                </div>
            </div>

        </div>
    </div>
</body>
<script>
    const numbersInput = document.getElementById('numbers');
    const targetInput = document.getElementById('capacity');
    let currentAction = ''; // 用于存储当前动作字符串

    document.getElementById('start-button').addEventListener('click', function() {
        const numbers = numbersInput.value;
        const target = targetInput.value;
        currentAction = 'begin'; // 设置当前动作为 "begin"
        sendDataToBackend(numbers, target, currentAction);
    });

    document.getElementById('next-button').addEventListener('click', function() {
        currentAction = 'next';
        sendDataToBackend('', '', currentAction);
    });

    document.getElementById('end-button').addEventListener('click', function() {
        currentAction = 'end'; // 设置当前动作为 "end"
        sendDataToBackend('', '', currentAction);
    });

    function sendDataToBackend(numbers, capacity, action) {
        fetch('/Knap_Backtrak', {
            method: 'POST',
            headers: {
                'Content-Type': 'application/json'
            },
            body: JSON.stringify({ numbers: numbers, capacity: capacity, action: action })
        })
        .then(response => response.json())
        .then(data => {
            // 处理后端返回的数据，更新页面
            updateUI(data);
        })
        .catch(error => console.error('Error:', error));
    }
    function delay(ms) {
        return new Promise(resolve => setTimeout(resolve, ms));
    }
    async function updateUI(data){
        let list = data.list;
        let list_len = data.len;
        for (let i = 0; i < list_len; i++) {
            document.getElementById('output-tape1').innerHTML  = list[i][0];
            document.getElementById('output-tape2').innerHTML  = list[i][1];
            document.getElementById('output-tape3').innerHTML  = list[i][2];
            
            document.getElementById('stack-text').innerHTML  = list[i][3];
            await delay(500);
        }
    }
</script>
</body>
</html>

以上是对应网页的html代码

Answer 1

以下内容由AIGC及阿里嘎多学长共同生成、有用望采纳：

---

根据您提供的代码和问题描述，我注意到了几点可能的问题所在，并提供了一些建议和代码示例来帮助您解决问题。

1. 右支上界计算问题： 您的bound函数中，在计算上界时，如果遇到self.inputweight[i]为0的情况，将会导致除以0的错误。此外，上界的计算逻辑可能需要调整以确保正确性。

2. backtrack函数的结束条件： 当i==n时，您应该更新最优解，而不是使用return结束函数。否则，这将导致函数提前退出，错过后续可能的更优解。

3. 代码逻辑和结构： 您的代码中存在一些可能影响性能和可读性的问题。例如，show函数可能会生成大量的输出，这在实际运行中可能不是必需的。此外，类中的许多变量和方法可能需要重新组织以提高效率。

下面是针对上述问题的一些代码修改建议：

修改后的bound函数

def bound(self, i):
    leftw = self.capacity - self.curweight
    b = self.curvalue
    while i < len(self.inputweight) and leftw >= self.inputweight[i]:
        leftw -= self.inputweight[i]
        b += self.inputvalue[i]
        i += 1
    # 避免除以0，并使用贪婪策略选择剩余价值与重量比最大的物品
    if i < len(self.inputweight) and leftw > 0:
        max_ratio = 0
        for j in range(i, len(self.inputweight)):
            if self.inputweight[j] <= leftw:
                ratio = self.inputvalue[j] / self.inputweight[j]
                if ratio > max_ratio:
                    max_ratio = ratio
        b += max_ratio * leftw if max_ratio > 0 else 0
    return b

修改后的backtrack函数的结束条件

if i == n:
    # 更新最优解
    if self.curvalue > self.bestvalue:
        self.bestvalue = self.curvalue
        self.bestsolution = current_solution[:]
    # 返回当前解的值，而不是结束函数
    return

其他建议

• 考虑移除或简化show函数，因为它可能会生成大量的输出，影响程序性能。
• 检查get_input函数中是否有不必要的复杂性，简化输入处理逻辑。
• 确保在递归调用前后正确地更新和恢复状态，避免状态污染。

请注意，这些修改建议是基于您提供的代码和描述进行的分析。实际问题可能需要更详细的调试和测试来确定。如果这些建议没有解决您的问题，或者您需要进一步的帮助，请提供更多的信息或者具体的错误输出。