2 hui201561 Hui201561 于 2015.06.26 21:37 提问

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

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

2个回答

caozhy
caozhy   Ds   Rxr 2015.06.26 22:34
Hui201561
Hui201561 在此谢谢啦 感激感激感激 雪中送碳啊…
2 年多之前 回复
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 谢谢你的帮忙 感激不尽
2 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片