鱼C论坛

 找回密码
 立即注册
查看: 1849|回复: 1

为什么我写的程序老是崩溃,跪求大神帮忙看一下(回朔法求0/1背包问题)

[复制链接]
发表于 2018-11-5 23:56:52 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
#include<iostream>
using namespace std;
int n;//物品个数
int BackpackVolume;//背包容量
int maxValue;//最大价值
int *weight = new int[n];//物品的重量
int *value = new int[n];//物品的价值
int *bestPath = new int[n];//最佳路径
int *judge = new int[2]; //判断左右分支
int currentWeight=0;//当前重量
int currentValue=0;//当前价值
void dfs(int i) {
        
        if(i>n){
                if (currentValue > maxValue) {
                        maxValue = currentValue;
                        for(i=1;i<=n;i++){
                                bestPath[i] = judge[i];
                        }
                }
        }
        else
        {
                for (int j = 1; j >= 0; j--) {
                        judge[i] = j;
                        if (currentWeight + weight[i]* judge[i] <= BackpackVolume) {

                                currentWeight += weight[i] * judge[i];
                                currentValue += value[i] * judge[i];
                                dfs(i + 1);
                                currentWeight-= weight[i] * judge[i];
                                currentValue -= value[i]* judge[i];
                        }
                
                }
        }
}

int main()
{
        int i;
        maxValue = 0;
        cout << "请输入背包最大容量:" << endl;;
        cin >> BackpackVolume;
        cout << "请输入物品个数:" << endl;
        cin >> n;
        cout << "请依次输入物品的重量:" << endl;
        for (i = 1; i <= n; i++)
                cin >> weight[i];
        cout << "请依次输入物品的价值:" << endl;
        for (i = 1; i <= n; i++)
                cin >> value[i];
        dfs(1);
        cout << "最大价值为:" << endl;
        cout << maxValue << endl;
        cout << "被选中的物品的标号依次是:" << endl;
        for (i = 1; i <= n; i++){
                if (bestPath[i] == 1)
                        cout << i << " ";
        }        
        cout << endl;
        return 0;
}
360截图20181105235507361.jpg
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-11-6 00:23:37 | 显示全部楼层
第55行一运行就崩溃???????????????????????
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-10-2 20:28

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表