部分背包问题
题目描述
给定一个最大容量为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;
}