01package

01-package

时间限制 : 1000 ms 内存限制 : 32 MB

提交次数 : 47 通过次数 : 12

题目描述

给定一个背包的容量k，给定n个物品的体积和价值，物品不可分割，将n个物品中选若干个物品放入背包，求背包内物品的最大价值总和，在价值总和最大的前提下求背包内的最小物品个数c。

输入描述

第一行是一个整数t，表示测试数据的组数t。
对于每组测试数据，第一行是两个整数n和k,表示物品的个数和背包的容量；
接下来n行，每行两个整数，分别是物品的价值和体积。

输出描述

输出背包内物品的最大价值v，在价值最大的前提下求背包内的最小物品个数c，中间用一个空格隔开。

样例输入

样例输出

10 1

作者

xiewenxiu

代码提交 | 题目列表 | 统计

#include <iostream>
#define MAX 1002
using namespace std;
struct node
{
    int num;
    int sv;
}dp[MAX];
struct nodeData
{
    int value;
    int w;
}data[MAX];
int n,c,t;
void Init()
{
    int i;
    scanf("%d%d",&n,&c);
    for(i=1;i<=n;i++)
        scanf("%d%d",&data[i].value,&data[i].w);
}
int GetMin(int a,int b)
{
    if(a>b)
        return b;
    else
        return a;
}
void Knapsack()
{
    int i,j;
    for(i=0;i<data[n].w;i++)  //初始化
    {
        dp[i].sv=0;
        dp[i].num=0;
    }
    for(;i<=c;i++)
    {
        dp[i].sv=data[n].value;
        dp[i].num=1;
    }
    for(i=n-1;i>=1;i--)
        for(j=c;j>=data[i].w;j--)  //for(j=m;j>=data[i].w;j--)也可以
        {
            if(j>=data[i].w)
            {
                int temp=dp[j-data[i].w].sv+data[i].value,tNum=dp[j-data[i].w].num;
                if(dp[j].sv<temp)
                {
                    dp[j].sv=temp;
                    dp[j].num=tNum+1;
                }
                else if(dp[j].sv==temp)
                {
                    dp[j].num=GetMin(dp[j].num,tNum+1);
                }
            }
        }
    printf("%d %d\n",dp[c].sv,dp[c].num);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        Init();
        Knapsack();
    }
    return 0;
}