OR114. 乔乔的包
描述
玥玥带乔乔一起逃亡,现在有许多的东西要放到乔乔的包里面,但是包的大小有限,所以我们只能够在里面放入非常重要的物品。现在给出该种物品的数量、体积、价值的数值,希望你能够算出怎样能使背包的价值最大的组合方式,并且输出这个数值,乔乔会非常感谢你。
输入描述
第1行有2个整数,物品种数n和背包装载体积v;输出描述
仅包含一个整数,即为能拿到的最大的物品价值总和。示例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; }