题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2546
思路：刚开始直接把背包的容量搞为m-5+max1（max1的值为最贵的菜的价格），因为他最多的能花这么多，结果错了，应该把最大的单独提出来，用5块来买,剩下的钱做背包
AC代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>
const
int
inf
=
0x3f3f3f3f;
//1061109567
typedef
long
long
LL;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using
namespace
std;
int
dp[
1000];
int
a[
1010];
int
main()
{
int
n;
while(
scanf(
"%d",
&
n)
&&
n)
{
memset(
dp,
0,
sizeof(
dp));
int
max1
=
-
1;
int
k;
for(
int
i
=
1;
i
<=
n;
i
++)
{
scanf(
"%d",
&
a[
i]);
if(
a[
i]
>
max1)
{
max1
=
a[
i];
k
=
i;
}
}
int
x;
scanf(
"%d",
&
x);
if(
x
<
5)
{
printf(
"%d\n",
x);
continue;
}
x
-=
5;
for(
int
i
=
1;
i
<=
n;
i
++)
{
if(
i
==
k)
continue;
for(
int
j
=
x;
j
>=
a[
i];
j
--)
{
dp[
j]
=
max(
dp[
j],
dp[
j
-
a[
i]]
+
a[
i]);
}
}
printf(
"%d\n",
x
+
5
-
dp[
x]
-
max1);
}
return
0;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
错误代码：（这个会造成价值最大的有可能没有选，逻辑不对）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>
const
int
inf
=
0x3f3f3f3f;
//1061109567
typedef
long
long
LL;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using
namespace
std;
int
dp[
1060];
int
a[
1010];
int
main()
{
int
n;
while(
scanf(
"%d",
&
n)
&&
n)
{
memset(
dp,
0,
sizeof(
dp));
int
max1
=
0;
for(
int
i
=
1;
i
<=
n;
i
++)
{
scanf(
"%d",
&
a[
i]);
if(
a[
i]
>
max1)
max1
=
a[
i];
}
int
cost;
scanf(
"%d",
&
cost);
int
x
=
cost;
if(
cost
<
5)
{
printf(
"%d\n",
cost);
continue;
}
cost
=
cost
-
5
+
max1;
for(
int
i
=
1;
i
<=
n;
i
++)
{
for(
int
j
=
cost;
j
>=
a[
i];
j
--)
{
dp[
j]
=
max(
dp[
j],
dp[
j
-
a[
i]]
+
a[
i]);
}
}
printf(
"%d\n",
x
-
dp[
cost]);
}
return
0;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
原网站版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15740602/5543538
