2 hui201561 Hui201561 于 2015.06.26 21:37 提问

用C语言解决数据结构的背包问题

求大神解答…在此谢谢比较急…希望大家能够帮帮忙哇…这是我们的课程设计不怎么会
图片说明图片说明

2个回答

caozhy
caozhy   Ds   Rxr 2015.06.26 22:34
Hui201561
Hui201561 在此谢谢啦 感激感激感激 雪中送碳啊…
大约 3 年之前 回复
wangyaninglm
wangyaninglm   Ds   Rxr 2015.06.26 22:35
 //背包问题:有m件物品和一个承重为t的背包。第i件物品的重量是w[i],价值是v[i]。
//求解将哪些物品装入背包可使这些物品的重量总和不超过背包承重量t,且价值总和最大。
#include <stdio.h>
#include <conio.h>
#include <string.h>

int f[1010],w[1010],v[1010];//f记录不同承重量背包的总价值,w记录不同物品的重量,v记录不同物品的价值

int max(int x,int y){//返回x,y的最大值
    if(x>y) return x;
    return y;
}

int main(){
    int t,m,i,j;
    memset(f,0,sizeof(f));  //总价值初始化为0
    scanf("%d %d",&t,&m);  //输入背包承重量t、物品的数目m
    for(i=1;i<=m;i++)
        scanf("%d %d",&w[i],&v[i]);  //输入m组物品的重量w[i]和价值v[i]
    for(i=1;i<=m;i++){  //尝试放置每一个物品
        for(j=t;j>=w[i];j--){
            f[j]=max(f[j-w[i]]+v[i],f[j]);
            //在放入第i个物品前后,检验不同j承重量背包的总价值,如果放入第i个物品后比放入前的价值提高了,则修改j承重量背包的价值,否则不变
        }
    }
    printf("%d",f[t]);  //输出承重量为t的背包的总价值
    printf("\n");
    getch();
    return 0;
}
Hui201561
Hui201561 谢谢你的帮忙 感激不尽
大约 3 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
数据结构-背包问题
背包问题
背包问题C++用栈解决
C++用栈来解决背包问题 经典数据结构问题 代码精简
算法与数据结构-贪心算法及背包问题解决
算法,五大常用算法,贪心算法,背包问题
[算法]数据结构算法背包问题解法之递归解法,C语言实现
今天讲背包问题的最后一种解法,递归解法,这种解法也是目前算法教材上讲的基本解法之一,如果你有一本关于这类算法的书籍,一般都可以找到你想要的算法,背包问题具体是什么,大家可以参考我的以前的文章,可以直接到下面的相关链接里面找到,我在最近发布关于背包问题的基本解法,动态规划解法,回溯解法,大家可以直接参照我的页面链接,如果具体还有问题不懂的话,也非常欢迎大家留言好的,讲一讲递归算法,我提供的算法是使用
动态规划解0-1背包问题(C语言版)
这学期开的算法课,感觉好难,光这个问题就弄了好久,我这里的代码非本人原创代码,都是借鉴网上的代码按自己的理解加以改进的,原网页地址 为http://www.cnblogs.com/qinyg/archive/2012/04/26/2471829.html 问题描述: 给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ,背包的容量为C。问应该如何选择装入背包的物品,使得转入
0-1背包问题分支界限法求解-C语言实现
完全版分支界限法求解背包问题,易于理解 分支界限法0-1背包问题
[算法]背包问题的经典算法和贪心算法解答,C语言实现
圣诞前夜讲点比较具有圣诞感觉的算法,背包问题算法,这里我写了经典算法和贪心算法两种解决方法,因为时间不多,所以给出的数组是已经排序的,因为贪心算法可能要用得到,经典算法因为是一个一个比较,因此排序也就没有那么重要了,可能两种算法的最终运行效果一样的,朋友们调试的时候记得修改我给出的测试数组,今天实在太忙了,贪心使用的排序算法没有写,留着以后给大家讲排序算法的时候使用吧,圣诞快乐,诸位朋友们。背包问
贪心算法解决背包问题
已知有n种物品和一个可容纳M重量的背包,每种物品i的重量为 。假定将物品i的一部分 放入背包就会得到 的效益,这里, , 。显然,由于背包容量是M,因此,要求所有选中要装入背包的物品总重量不得超过M.。如果这n件物品的总重量不超过M,则把所有物品装入背包自然获得最大效益。现需解决的问题是,这些物品重量的和大于M,该如何装包。
用回溯法解决01背包问题C语言实现
01背包问题是一个很经典的问题,在这里我用回溯法解决。希望大家一起来探讨呀!
贪心法解决背包问题c语言代码
用贪心法解决背包问题的源代码,在vc++环境下也可以运行