问题:
考试由 N 个问题组成。 N 题的分数分别为 m1、m2、m3、.. mN。 Jam 正在参加考试,他想最大化自己的分数。 然而,他需要一些时间来解决每个问题。他解决问题所花费的时间分别是 t1, t2, t3, .. tN。 考试总共持续时间 T。 但杰姆的老师非常聪明,她知道杰姆会找到获得最高分的方法。所以,为了迷惑杰姆,她还向他提出了一份奖金—— 提议是,Jam 可以选择一个问题,他可以将该问题的分数加倍。 现在,杰姆确实很困惑。帮助他找出他可以获得的最大分数。
约束
1<=N<=1000
1<=T<=10000
1<=mi<=100000
1<=ti<=10000
我尝试了这个问题here并提出了以下算法:
既然问题如此,我们就可以选择一个问题,他可以将该问题的分数加倍。
因此,为了选择该问题,我应用了贪婪方法,即......
- 应选择具有较大(分数/时间)比率的问题,他可以将该问题的分数加倍。
如果该比例也相同,则应选择分数较大的问题。
据我理解这个问题,剩下的就是简单的背包。 我尝试了以下实现,但得到了错误的答案。 对于给定的测试用例,我的代码给出了正确的输出
3 10 1 2 3 4 3 4
我已经尝试了评论部分中给出的测试用例,我的代码给出了 16 作为输出,但答案应该是 18
3
9
9 6 5
8 5 3
暴力方法会超出时间限制,因为解决复杂度为 O(nW) 的 N 个背包将给出 O(n^2 W) 的总体时间复杂度 我认为可以针对这个问题开发更具体的算法。 还有人有比这更好的主意吗?
谢谢
#include<iostream>
#include<cstdio>
using namespace std;
int T[2][10002];
int a[1000002],b[100002];
float c[100002];
int knapSack(int W,int val[],int wgt[],int n)
{
int i,j;
for(i=0;i<n+1;i++)
{
if(i%2==0)
{
for(j=0;j<W+1;j++)
{
if(i==0 || j==0)
T[0][j]=0;
else if(wgt[i-1]<=j)
T[0][j]=max(val[i-1]+T[1][j-wgt[i-1]],T[1][j]);
else
T[0][j]=T[1][j];
}
}
else
{
for(j=0;j<W+1;j++)
{
if(i==0 || j==0)
T[1][j]=0;
else if(wgt[i-1]<=j)
T[1][j]=max(val[i-1]+T[0][j-wgt[i-1]],T[0][j]);
else
T[1][j]=T[0][j];
}
}
}
if(n%2!=0)
return T[1][W];
else
return T[0][W];
}
int main()
{
int n,i,j,index,t,mintime,maxval;
float maxr;
cin>>n;
cin>>t;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
cin>>b[i];
maxr=0;
index=0;
mintime=b[0];
maxval=a[0];
for(i=0;i<n;i++)
{
c[i]=(float)a[i]/b[i];
if(c[i]==maxr && b[i]<=t)
{
if(a[i]>=maxval)
{
maxval=a[i];
mintime=b[i];
index=i;
}
}
else if(c[i]>maxr && b[i]<=t)
{
maxr=c[i];
maxval=a[i];
mintime=b[i];
index=i;
}
}
a[index]=a[index]*2;
int xx=knapSack(t,a,b,n);
printf("%d\n",xx);
}
最佳答案
要解决这个问题,我们先看the wikipedia article on the Knapsack problem它为常规问题提供了动态规划解决方案:
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for j from 0 to W do
m[0, j] := 0
end for
for i from 1 to n do
for j from 0 to W do
if w[i] <= j then
m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
else
m[i, j] := m[i-1, j]
end if
end for
end for
(正如文章所述,您可以通过使用一维数组 m 而不是二维数组来减少内存使用量)。
现在我们可以用这个想法来解决扩展问题。您可以计算两个表:您可以计算 m0 和 m1,而不是 m。 m0[i, w] 存储使用前 i 个权重(在您的情况下为时间)最多为 w 的项目获得的最大值,不使用双计分问题。类似地,m1 存储使用权重(在您的情况下为时间)最多为 w 的前 i 个项目以及使用双计分问题获得的最大值。
更新规则更改为:
if w[i] <= j then
m0[i, j] := max(m0[i-1, j], m0[i-1, j-w[i]] + v[i])
m1[i, j] := max(m1[i-1, j], m1[i-1, j-w[i]] + v[i], m0[i-1, j-w[i]] + 2 * v[i])
else
m0[i, j] = m0[i-1, j]
m1[i, j] = m1[i-1, j]
end if
与常规问题一样,您可以使用两个一维数组而不是两个二维数组来减少内存使用量。
关于arrays - 编程竞赛中的背包变式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23719251/