Codeforce 730J(贪心+01背包)

链接：点击打开链接

题意：给n个瓶子，给出每个瓶子剩余水的容量和每个瓶子的体积，问最少需要使用的瓶子数量能装完剩下全部的水，每次改变1单位的水花费1单位时间，并输出最少时间

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int dp[105][10005];
struct node{
int le,val;
friend bool operator<(node a,node b){
if(a.val==b.val)
return a.le>b.le;
return a.val>b.val;
}
}s[105];
int main(){
int n,i,j,k,ans1,ans2,tmp,sum;
while(scanf("%d",&n)!=EOF){
sum=0;
for(i=1;i<=n;i++){
scanf("%d",&s[i].le);
sum+=s[i].le;
}
for(i=1;i<=n;i++)
scanf("%d",&s[i].val);
sort(s+1,s+n+1);
//因为要求瓶子数目最小。所以
tmp=0;
//直接排序求前缀，求出最小的
for(i=1;i<=n;i++){
//瓶子数目，但是不一定就用这
tmp+=s[i].val;
//几个瓶子，因此用dp判断
if(tmp>=sum){
ans1=i;
break;
}
}
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
//dp[i][j]表示选了i个瓶子，已经
for(i=1;i<=n;i++){
//装了j体积，i个瓶子的最大容量
for(j=sum;j>=0;j--){
for(k=1;k<=i;k++){
if(j>=s[i].le&&dp[k-1][j-s[i].le]!=-1)
dp[k][j]=max(dp[k][j],dp[k-1][j-s[i].le]+s[i].val);
}
}
}
for(i=sum;i>=0;i--){
//找出ans1个瓶子能装所有水时间的最小值
if(dp[ans1][i]>=sum){
ans2=sum-i;
break;
}
}
printf("%d %dn",ans1,ans2);
}
return 0;
}

最后

以上就是搞怪饼干为你收集整理的Codeforce 730J(贪心+01背包)的全部内容，希望文章能够帮你解决Codeforce 730J(贪心+01背包)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。