贪心背包和0-1背包问题

2024-09-01 17:58
文章标签 问题 贪心 背包

本文主要是介绍贪心背包和0-1背包问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

0-1背包问题
//#include<iostream>
//using namespace std;
//int w[1000],v[1000];
//int f[1000];
//int main()
//{
//    int n;//物品数量
//    int c;//背包容量
//    while(cin>>n)
//    {
//        for(int i=0;i<n;i++)
//        {
//            cin>>w[i];//重量
//            cin>>v[i];//价值
//        }
//        memset(f,0,sizeof(f));
//        for(int i=0;i<n;i++)
//        {
//            for(int j=c;j>=v[i];j--)
//            {
//                f[j]=max(f[j],f[j-w[i]+v[i]);
//            }
//        }
//        cout<<f[c]<<endl;
//    }

//}


背包问题
#include<iostream>
using namespace std;
struct goodinfo
{
    float p;//物品价值
    float w;//物品重量
    float x;//物品该放的数量
    int flag;//物品编号
};//物品信息结构体
void insertionsort(goodinfo goods[],int n)//插入排序,按pi/wi价值进行排序
{
    int i,j;
    for(j=2;j<=n;j++)
    {
        goods[0]=goods[j];
        i=j-1;
        while(goods[0].p>goods[i].p)
        {
            goods[i+1]=goods[0];
        }
        goods[i+1]=goods[i];i--;
    }
}
void bag(goodinfo goods[],float M,int n)
{
    float cu;
    int i,j;
    for(i=1;i<=n;i++)
        goods[i].x=0;
    cu=M;//背包剩余容量
    for(i=1;i<n;i++)
    {
        if(goods[i].w<cu)//若不超过容量,增加物品
        {
            goods[i].x=1;
            cu-=goods[i].w;//确定背包新的剩余容量
        }
        else
        {
            goods[i].x=0;
        }
        for(j=2;j<=n;j++)//按物品编号降序排列
        {
            goods[0]=goods[j];
            i=j-1;
            while(goods[0].flag<goods[i].flag)
            {
                goods[i+1]=goods[i];
                i--;
            }
        }
        goods[i+1]=goods[0];
    }
    cout<<"最优解为:"<<endl;
    for(i=1;i<=n;i++)
    {
        cout<<"第"<<i<<"件物品要放";
        cout<<goods[i].x<<endl;
    }
}
int main()
{
    cout<<"贪心算法背包问题"<<endl;
    int j,n;
    float M;
    goodinfo*goods;//定义指针
    while(j)
    {
        cout<<"请输入物品总重量";
        cin>>n;
        goods=new struct goodinfo[n+1];
        cout<<"输入背包最大容量";
        cin>>M;
        cout<<endl;
        int i;
        for(i=1;i<=n;i++)
        {
            goods[i].flag=i;
            cout<<"请输入第i件物品重量";
            cin>>goods[i].w;
            cout<<"请输入第"<<i<<"件物品利润";
            cin>>goods[i].p;
            goods[i].p=goods[i].p/goods[i].w;//重量比
            cout<<endl;
        }
        insertionsort(goods,n);
        bag(goods,M,n);
        cout<<"press 1 to run again"<<endl;
        cout<<"press 0 to exit"<<endl;
        cin>>j;


    }
}

这篇关于贪心背包和0-1背包问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1127655

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s