`
Lisajoy512
  • 浏览: 10255 次
  • 性别: Icon_minigender_2
  • 来自: 武汉
社区版块
存档分类
最新评论

非01背包问题

阅读更多
题目:四种类型的物品,体积分别为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;
}
0
0
分享到:
评论

相关推荐

    用贪心算法解非0-1背包问题

    贪心算法解背包问题,供读者参考,我想看看有没有动态规划算法的解决办法

    背包问题可视化

    【背包问题可视化】是一种在计算机科学中用于解决优化问题的经典算法,主要应用于资源分配和决策制定。这个项目是基于.NET框架实现的,并且利用ASP.NET技术进行可视化展示。通过使用`asp:table`控件,开发者创建了一...

    01背包问题(C#图形界面)

    01背包问题是一种经典的计算机科学优化问题,常用于求解有限资源下的最大效益问题。在这个问题中,我们有一个背包,其容量有限,需要在一系列物品中选择,每种物品都有一定的重量和价值,目标是使得装入背包的物品总...

    01背包大全(涵盖所有方法实现)

    但贪心法不能保证总是得到全局最优解,因为01背包问题具有非贪心最优性。 多个背包问题是指存在多个背包,每个背包有自己的容量,我们需要将物品分配到这些背包中,以最大化总价值。这个问题比单背包问题更复杂,...

    背包问题九讲2.0(13年修订版)

    #### 一、01背包问题 **1.1 题目** 给定N件物品和一个容量为V的背包,每件物品有一个固定的费用\( C_i \)和价值\( W_i \)。目标是从这些物品中选择若干件放入背包,使得背包内物品的总价值最大,并且不超过背包的...

    分支定界算法求解0-1背包问题(附MATLAB代码).rar

    0-1背包问题是一种经典的组合优化问题,在许多实际场景中都有应用,比如资源分配、生产计划、投资组合优化等。该问题的基本设定是:有一组物品,每件物品都有一个重量和一个价值,且每件物品只能选择放入背包或者不...

    信息学奥赛背包问题九讲

    1. **01背包问题**:这是最基础的背包问题,每个物品最多只能放入一次。问题通常涉及到确定如何在不超过背包容量的前提下,选择物品以最大化总价值。 2. **完全背包问题**:与01背包问题不同,每种物品可以无限次放...

    回溯法背包问题非递归实现

    回溯法递归实现和非递归实现.解用向量表示,解分量集合有1、2两个元素,一表示放入背包,二表示不放入背包。具有一般性。

    基于Python和粒子群算法解决01背包问题并进行可视化.zip

    01背包问题是一种经典的组合优化问题,广泛存在于资源分配、任务调度等领域。在这个问题中,我们有一组物品,每个物品都有一个重量和一个价值,目标是确定每种物品放入一个容量有限的背包中的数量,以使背包内的总...

    各种背包算法详解

    01背包问题是最基础的背包问题类型,每个物品要么完全放入背包(占满1个单位容量),要么不放。给定一组物品,每种物品都有重量和价值,目标是确定每种物品的数量,使得装入背包的物品总重量不超过背包的最大容量,...

    0-1背包问题 动态规划 分支限界 回溯 贪心四种方法

    然而,0-1背包问题具有非贪心性质,即单纯按价值密度(价值/重量)选取物品通常不能得到全局最优解。尽管如此,贪心算法在某些特殊情况下可能得到较好的结果,如物品重量可无限分割时。 以上四种方法各有优缺点。...

    动态规划背包问题9讲

    同时,可以通过将问题转化为01背包问题来求解,将每种物品视为多个不同重量的物品,每个物品的重量是原物品的权重乘以其数量。 **多重背包问题** 多重背包问题则介于01背包和完全背包之间,每种物品有一定的数量...

    遗传算法求解0-1背包问题

    附带的文档"遗传算法求解01背包问题.doc"和"Pudn.com"网站上的资料可能提供了更详细的算法实现细节和代码解析。而"Solving the 0-1 Knapsack Problem with Genetic Algorithms.pdf"可能是学术论文,详细讨论了遗传...

    基于Matlab的0_1背包问题的动态规划方法求解

    背包问题作为计算机科学中的经典难题之一,属于NP-hard(非确定性多项式时间难度)问题类别,在多个领域中都有重要应用,例如资源分配、投资决策、预算控制以及项目选择等。该问题的核心在于如何在有限的背包容量下...

    matlab遗传算法解决背包问题

    其中,背包问题是一个典型的组合优化问题,它涉及到在一个有限的容量限制下,如何选择物品以最大化总价值。这个问题在资源分配、任务调度等领域有着广泛应用。本文将深入探讨如何使用MATLAB中的遗传算法来解决背包...

    毕业论文基于遗传算法的01背包问题研究.doc

    【基于遗传算法的01背包问题研究】 0-1背包问题是一种经典的组合优化问题,广泛应用于资源分配、项目选择和投资决策等领域。该问题的基本设定是:有一个容量有限的背包,以及一系列物品,每个物品都有自己的重量和...

    背包九讲(详细)

    **转化为01背包**:将多重背包问题转化为01背包问题的关键在于构建虚拟物品集,使得每个虚拟物品对应原物品的一个数量选择,从而将原问题转换为标准的01背包问题,便于使用已有的算法框架求解。 **O(VN)算法**:...

Global site tag (gtag.js) - Google Analytics