01-package

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

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

题目描述

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

输入描述

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

输出描述

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

样例输入

1 3 10 4 5 6 5 10 10

样例输出

10 1

作者

xiewenxiu

题目添加

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

#include <iostream>#define MAX 1002using 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; }

转载于:https://www.cnblogs.com/forever4444/archive/2009/05/08/1452890.html

相关资源：0-1背包问题需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。