列表

详情


OR114. 乔乔的包

描述

玥玥带乔乔一起逃亡,现在有许多的东西要放到乔乔的包里面,但是包的大小有限,所以我们只能够在里面放入非常重要的物品。现在给出该种物品的数量、体积、价值的数值,希望你能够算出怎样能使背包的价值最大的组合方式,并且输出这个数值,乔乔会非常感谢你。

输入描述

第1行有2个整数,物品种数n和背包装载体积v;

第2行到i+1行每行3个整数,为第i种物品的数量m、体积w、价值s。

输出描述

仅包含一个整数,即为能拿到的最大的物品价值总和。

示例1

输入:

2 10
3 4 3
2 2 5

输出:

13

说明:

选第一种一个,第二种两个,结果为3x1+5x2=13。

原站题解

C 解法, 执行用时: 2ms, 内存消耗: 432KB, 提交时间: 2020-09-08

#include<stdio.h>
int max(int a, int b)
{
  return a>b? a:b;
}
int main()
{
  int n,v;
  int i,j,k;
  int m[2005],w[2005],s[2005];
  int dp[505];
 // memset(dp,0,sizeof(dp));
  scanf("%d %d",&n,&v);
  for(i=0;i<n;i++)
  {
    scanf("%d %d %d",&m[i],&w[i],&s[i]);
    for(j=0;j<m[i];j++)
    {
      for(k=v;k>=w[i];k--)
      {
        dp[k]=max(dp[k],dp[k-w[i]]+s[i]);
      }
    }
  }
  printf("%d",dp[v]);
  return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 472KB, 提交时间: 2020-10-31

#include<bits/stdc++.h>
using namespace std;
typedef struct value
{
    int m;
    int w;
    int s;
};
bool cmp(const value&x,const value&y)
{
    return double(double(x.s)/double(x.w)) > double(double(y.s)/double(y.w));
}
int main()
{
    int n,v;
    cin>>n>>v;
    vector<value>ss;
    for(int i=0;i<n;i++)
    {
        value k;
        cin>>k.m>>k.w>>k.s;
        ss.push_back(k);
    }
    sort(ss.begin(),ss.end(),cmp);
    int sumvalue=0;
    int currentw=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<ss[i].m;j++)
        {
            if(currentw+ss[i].m * ss[i].w < v)
            {
                currentw+=ss[i].m * ss[i].w;
                sumvalue+=ss[i].m * ss[i].s;
                break;
            }
            else
            {
                if(currentw+ss[i].w > v) break;
                else
                {
                    currentw+=ss[i].w;
                sumvalue+= ss[i].s;
                }
            }
        }
    }
    cout<<sumvalue<<endl;
    return 0;
}

上一题