[1372] Do What
時間限制: 1000 ms 內存限制: 65535 K
問題描述
There are n numbers of business, different business will cost you different times. But you need not to finish all of them, just it is ok when you finish some of them that you spend more than T minutes(do not include T minutes).
So, can you find the way to cost the minimum time when pass T times?
輸入
Input until EOF.
First line will contain a positive integer n(1 <= n <= 100) means the number of businesses.
Next line follows n positive integers ti(1 <= ti <= 10), means the time of each business you will cost.
Last line is a integer T(1 <= T <= 1000).
輸出
The minimum time of you cost, if there is no answer, print '-1'.
樣例輸入
3
1 2 3
10
3
1 4 7
6
樣例輸出
-1
7
提示
無來源
Hungar操作
題意： 從n個數中取出任意個 數字 使得這些數字的和大於T且和最小
思路：
01背包 背包過程中取離T最近的值
詳細看代碼
[cpp]
#include<stdio.h>
#include<string.h>
int n,t,ans;
int val[105];
int dp[10000];
void _01bag(int v)
{
int i,j;
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
for(j=v;j>=val[i];j--)
if(dp[j]<dp[j-val[i]]+val[i])
{
dp[j]=dp[j-val[i]]+val[i];
if(dp[j]>t&&ans>dp[j]-t) ans=dp[j]-t;
}
printf("%d\n",ans+t);
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
ans=999999999;
int sum=0;
for(i=0;i<n;i++)
{
scanf("%d",&val[i]);
sum+=val[i];
}
scanf("%d",&t);
if(sum>t)
_01bag(sum);
else printf("-1\n");
}
return 0;
}
#include<stdio.h>
#include<string.h>
int n,t,ans;
int val[105];
int dp[10000];
void _01bag(int v)
{
int i,j;
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
for(j=v;j>=val[i];j--)
if(dp[j]<dp[j-val[i]]+val[i])
{
dp[j]=dp[j-val[i]]+val[i];
if(dp[j]>t&&ans>dp[j]-t) ans=dp[j]-t;
}
printf("%d\n",ans+t);
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
ans=999999999;
int sum=0;
for(i=0;i<n;i++)
{
scanf("%d",&val[i]);
sum+=val[i];
}
scanf("%d",&t);
if(sum>t)
_01bag(sum);
else printf("-1\n");
}
return 0;
}
