题目:四种类型的物品,体积分别为2,3,5,6,价值分别为4,7,9,11.背包容量为8,每种物品的最大数量不限制
#include <iostream>
using namespace std;
#define MAXSIZE 8
#define NUM 4
int main(void)
{
int size_value[NUM+1][2] = {{0,0},{2,4},{3,7},{5,9},{6,11}};
int solution[NUM+1][MAXSIZE+1];
int v[NUM+1];
for(int p=0;p<=NUM;p++)
{
for (int q=0;q<=MAXSIZE;q++)
{
solution[p][q]=0;
}
}
for(int i=0;i<=NUM;i++)
v[i] = 0;
for(int i=1;i<=NUM;i++)
{
for(int j=1;j<=MAXSIZE;j++)
{
v[i] = 0;
solution[i][j] = solution[i-1][j];
for(v[i]=0;v[i]*size_value[i][0] <= j;v[i]++)
{
if(solution[i][j] <= (solution[i-1][j-v[i]*size_value[i][0]] + v[i]*size_value[i][1])) //要注意的便是这个地方,01背包是solution[i-1][j]来比较,但是非01背包则需用solution[i][j]来比较,已记录得到最大值
{
solution[i][j] = solution[i-1][j-v[i]*size_value[i][0]] + v[i]*size_value[i][1];
}
}
}
}
for(int i=0;i<=NUM;i++)
{
for(int j=0;j<=MAXSIZE;j++)
{
cout<<solution[i][j]<<" ";
}
cout<<"\n";
}
/*for(int i=0;i<=NUM;i++)
cout<<v[i]<<" ";*/
while(1)
;
return 0;
}
分享到:
相关推荐
贪心算法解背包问题,供读者参考,我想看看有没有动态规划算法的解决办法
【背包问题可视化】是一种在计算机科学中用于解决优化问题的经典算法,主要应用于资源分配和决策制定。这个项目是基于.NET框架实现的,并且利用ASP.NET技术进行可视化展示。通过使用`asp:table`控件,开发者创建了一...
01背包问题是一种经典的计算机科学优化问题,常用于求解有限资源下的最大效益问题。在这个问题中,我们有一个背包,其容量有限,需要在一系列物品中选择,每种物品都有一定的重量和价值,目标是使得装入背包的物品总...
但贪心法不能保证总是得到全局最优解,因为01背包问题具有非贪心最优性。 多个背包问题是指存在多个背包,每个背包有自己的容量,我们需要将物品分配到这些背包中,以最大化总价值。这个问题比单背包问题更复杂,...
#### 一、01背包问题 **1.1 题目** 给定N件物品和一个容量为V的背包,每件物品有一个固定的费用\( C_i \)和价值\( W_i \)。目标是从这些物品中选择若干件放入背包,使得背包内物品的总价值最大,并且不超过背包的...
0-1背包问题是一种经典的组合优化问题,在许多实际场景中都有应用,比如资源分配、生产计划、投资组合优化等。该问题的基本设定是:有一组物品,每件物品都有一个重量和一个价值,且每件物品只能选择放入背包或者不...
1. **01背包问题**:这是最基础的背包问题,每个物品最多只能放入一次。问题通常涉及到确定如何在不超过背包容量的前提下,选择物品以最大化总价值。 2. **完全背包问题**:与01背包问题不同,每种物品可以无限次放...
回溯法递归实现和非递归实现.解用向量表示,解分量集合有1、2两个元素,一表示放入背包,二表示不放入背包。具有一般性。
01背包问题是一种经典的组合优化问题,广泛存在于资源分配、任务调度等领域。在这个问题中,我们有一组物品,每个物品都有一个重量和一个价值,目标是确定每种物品放入一个容量有限的背包中的数量,以使背包内的总...
01背包问题是最基础的背包问题类型,每个物品要么完全放入背包(占满1个单位容量),要么不放。给定一组物品,每种物品都有重量和价值,目标是确定每种物品的数量,使得装入背包的物品总重量不超过背包的最大容量,...
然而,0-1背包问题具有非贪心性质,即单纯按价值密度(价值/重量)选取物品通常不能得到全局最优解。尽管如此,贪心算法在某些特殊情况下可能得到较好的结果,如物品重量可无限分割时。 以上四种方法各有优缺点。...
同时,可以通过将问题转化为01背包问题来求解,将每种物品视为多个不同重量的物品,每个物品的重量是原物品的权重乘以其数量。 **多重背包问题** 多重背包问题则介于01背包和完全背包之间,每种物品有一定的数量...
附带的文档"遗传算法求解01背包问题.doc"和"Pudn.com"网站上的资料可能提供了更详细的算法实现细节和代码解析。而"Solving the 0-1 Knapsack Problem with Genetic Algorithms.pdf"可能是学术论文,详细讨论了遗传...
背包问题作为计算机科学中的经典难题之一,属于NP-hard(非确定性多项式时间难度)问题类别,在多个领域中都有重要应用,例如资源分配、投资决策、预算控制以及项目选择等。该问题的核心在于如何在有限的背包容量下...
其中,背包问题是一个典型的组合优化问题,它涉及到在一个有限的容量限制下,如何选择物品以最大化总价值。这个问题在资源分配、任务调度等领域有着广泛应用。本文将深入探讨如何使用MATLAB中的遗传算法来解决背包...
【基于遗传算法的01背包问题研究】 0-1背包问题是一种经典的组合优化问题,广泛应用于资源分配、项目选择和投资决策等领域。该问题的基本设定是:有一个容量有限的背包,以及一系列物品,每个物品都有自己的重量和...
**转化为01背包**:将多重背包问题转化为01背包问题的关键在于构建虚拟物品集,使得每个虚拟物品对应原物品的一个数量选择,从而将原问题转换为标准的01背包问题,便于使用已有的算法框架求解。 **O(VN)算法**:...