题目描述
有n种重量和价值分别为w[i],v[i]的物品，从这些物品中挑选总重量不超过W的物品，求挑出物品价值总和的最大值。在这里，每种物品可以挑选多次。 限制条件 1 <= n <=100 1<= w[i],v[i] <= 100 1<=W<=10000
输入
n
,w
w
[i
],v
[i
]
输出
价值总和的最大值
样例输入
3 7
3 4
4 5
2 3
样例输出
10
代码
#include
<algorithm
>
#include
<iostream
>
#include
<cstdio
>
using namespace std
;
const int
N = 1010;
int dp
[N][N];
int
W[N],V[N];
int
main()
{
int n
,m
;
scanf("%d%d",&n
,&m
);
for(int i
= 1;i
<=n
;i
++)
{
scanf("%d%d",&W[i
],&V[i
]);
}
for(int i
= 1;i
<=n
;i
++)
{
for(int j
= 0;j
<=m
;j
++)
{
for(int k
= 0;k
*W[i
]<=j
;k
++)
{
dp
[i
][j
] = max(dp
[i
][j
],dp
[i
-1][j
-k
*W[i
]]+k
*V[i
]);
}
}
}
printf("%d\n",dp
[n
][m
]);
return 0;
}
这个代码有三种循环，时间超限，然后想办法去掉k循环
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-2*v]+2*w , .....)
由上两式，可得出如下递推关系：
f[i][j]=max(f[i,j-v]+w , f[i-1][j])
优化后的代码
#include
<algorithm
>
#include
<iostream
>
#include
<cstdio
>
using namespace std
;
const int
N = 1010;
int dp
[N][N];
int
W[N],V[N];
int
main()
{
int n
,m
;
scanf("%d%d",&n
,&m
);
for(int i
= 1;i
<=n
;i
++)
{
scanf("%d%d",&W[i
],&V[i
]);
}
for(int i
= 1;i
<=n
;i
++)
{
for(int j
= 0;j
<=m
;j
++)
{
dp
[i
][j
] = dp
[i
-1][j
];
if(j
>=W[i
])
{
dp
[i
][j
] = max(dp
[i
][j
],dp
[i
][j
-W[i
]]+V[i
]);
}
}
}
printf("%d\n",dp
[n
][m
]);
return 0;
}
还可以再优化一下
#include
<algorithm
>
#include
<iostream
>
#include
<cstdio
>
using namespace std
;
const int
N = 1010;
int dp
[N];
int
W[N],V[N];
int
main()
{
int n
,m
;
scanf("%d%d",&n
,&m
);
for(int i
= 1;i
<=n
;i
++)
{
scanf("%d%d",&W[i
],&V[i
]);
}
for(int i
= 1;i
<=n
;i
++)
{
for(int j
= W[i
];j
<=m
;j
++)
{
dp
[j
] = max(dp
[j
],dp
[j
-W[i
]]+V[i
]);
}
}
printf("%d\n",dp
[m
]);
return 0;
}
再将输入输出优化一下
#include
<algorithm
>
#include
<iostream
>
#include
<cstdio
>
using namespace std
;
const int
N = 1010;
int dp
[N];
int
main()
{
int n
,m
;
scanf("%d%d",&n
,&m
);
for(int i
= 1;i
<=n
;i
++)
{
int
W,V;
scanf("%d%d",&W,&V);
for(int j
= W;j
<=m
;j
++)
{
dp
[j
] = max(dp
[j
],dp
[j
-W]+V);
}
}
printf("%d\n",dp
[m
]);
return 0;
}
