我是靠谱客的博主 安静芒果,这篇文章主要介绍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内容请搜索靠谱客的其他文章。

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

评论列表共有 0 条评论

立即
投稿
返回
顶部