0 1背包问题c语言版回溯法,0-1背包问题——回溯法

112 阅读 0 评论 74 点赞

我是靠谱客的博主安静芒果，这篇文章主要介绍0 1背包问题c语言版回溯法,0-1背包问题——回溯法，现在分享给大家，希望可以做个参考。

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。

问应如何选择装入背包的物品，使得在总重量不超过背包的容量C的前提下装入背包中物品的总价值最大？

package com.lanxi.demo1;

public class Package {

static int n = 5;//给定物品数

int capacity = 15;//背包容量

int[] weight = {3,6,1,2,7};//物品重量

double[] value = {6,5,9,2,7};//物品价值

int maxValue = 0;//最大价值

int tempValue;

int tempWeight;

int[] way = new int[n];//存放方式

static int[] bestWay = new int[n];//价值最大存放方式

public void BackTrack(int t){

//已经搜索到根节点

if(t>n-1){

if(tempValue > maxValue){

maxValue = tempValue;

for(int i=0;i

bestWay[i] = way[i];

}

return ;

}

//搜索左边节点

if(tempWeight + weight[t] <= capacity){

//总的放入的物品重量要小于背包

tempWeigh

以上就是安静芒果最近收集整理的关于0 1背包问题c语言版回溯法,0-1背包问题——回溯法的全部内容，更多相关0内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。