部分背包问题(贪心算法)

时间:2021-07-15 04:23:20

部分背包问题

题目描述

给定一个最大容量为m的背包和n种问题,有食盐、白糖、大米等。已知第i种食品最多有wi公斤,其价值为vi/公斤,编程确定一个装货方案,使得装入背包中的所有食品的总价值最大。

输入输出格式

输入格式:
第一行,两个整数m,n,表示背包容量和食品种类。

接下去n行,为每种食品的数量和价值

输出格式:
价值:%d   取:%d

输入输出样例

输入样例#1

5 3

2 3

4 5

3 6

输出样例#1

价值:6    取:3

价值:3    取:2


【代码】

#include<stdio.h>
int main(){

int w[1000],v[1000];//w为质量,v为价值,r为价值与质量的比
float r[1000];//r为价值与质量的比
int n;//物品的数量
int m; //背包的容量 

scanf("%d %d",&m,&n);   //输入背包总量和数量
for(int i=0;i<n;i++){
scanf("%d %d",&w[i],&v[i]);
}

for(int i=0; i<n; i++){
r[i]=v[i]*1.0/w[i];
}

for(int i=1;i<n;i++){
for(int j=0;j<n-i;j++){
if(r[j]<r[j+1]){
int x;
float y;
y=r[j];r[j]=r[j+1];r[j+1]=y;
x=w[j];w[j]=w[j+1];w[j+1]=x;
x=v[j];v[j]=v[j+1];v[j+1]=x;


}

int i=0;
while(m>0){
if(w[i]<=m){
m-=w[i];
printf("价值:%d取:%d\n",v[i],w[i]);
i++;
}
else{
printf("价值:%d取:%d\n",v[i],m);
m=0;
}

return 0;