南阳理工--103背包问题

背包问题

难度：3
描述
现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。
输入
第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；
随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。
输出
输出每组测试数据中背包内的物品的价值和，每次输出占一行。
样例输入
1
3 15
5 10
2 8
3 9
样例输出
65

题意:
给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。
首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。

代码:

# include <iostream>
# include <cstdio>

using namespace std;

void sort(int v[],int w[],int s);

int main(){

    int s,m;//s代表数据的组数,m代表背包的重量 
    int v[11],w[11];//v代表价值,w代表重量 
    int n;//数据的组数

    scanf("%d",&n);
    while(n--){

        scanf("%d%d",&s,&m);
        for(int i=0;i<s;i++){
            scanf("%d%d",&v[i],&w[i]);
        }

        sort(v,w,s);//排序,以单位价值排序 
    //  for(int i=0;i<s;i++){
    //      printf("%d   %d \n",v[i],w[i]);
    //  }
        int sum = 0;
        for(int i=0;i<s;i++){
            if(m>w[i]){
                m = m - w[i];
                sum+=w[i]*v[i];
            }else{
                sum+=m*v[i]; 
                break;
            } 
        }

        printf("%d\n",sum);
    } 


    return 0;
}

void sort(int v[],int w[],int s){//选择排序 

    int i,j,k,t;

    for(i=0;i<s-1;i++){
        k=i;
        for(j=i+1;j<s;j++){
            if(v[j]>v[k]) k=j;
        }
        t=v[k],v[k]=v[i],v[i]=t;
        t=w[k],w[k]=w[i],w[i]=t;
    } 
}

代码2:

#include<stdio.h>
#define max(a,b) a>b?a:b
int main()
{
    int n,s,m,v,w,i,j,k;
    scanf("%d",&n);
    while(n--)
    {
        int DP[25]={0};
        scanf("%d %d",&s,&m);
        for(i=0;i<s;i++)
        {
            scanf("%d %d",&v,&w);
            for(k=0;k<w;k++)
            for(j=m;j>0;j--)
                DP[j]=max(DP[j-1]+v,DP[j]);
        }
        printf("%d\n",DP[m]);
    }
}