题目描述
01背包(动态规划)
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
8
二维写法
代码
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int dp[1005][1005];
int main()
{
int n, vi, v[1005], w[1005];
scanf("%d%d", &n, &vi);
for (int i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
/*状态转移方程:f[i,j]=MAX{f[i-1,j],f[i-1][j-v[i]]+w[i]}*/
for(int i=1;i<=n;i++)
for (int j = 0; j <= vi; j++)//j不能大于背包容量
{
/*dp[i][j]表示只从前i个物品中选,并且总体积不超过j*/
/*dp[i-1][j]表示不含i的选法*/
/*dp[i - 1][j - v[i]] + w[i])表示含i的选法*/
dp[i][j] = dp[i - 1][j];
if (j >= v[i])
if (dp[i - 1][j] <= (dp[i - 1][j - v[i]] + w[i]))
dp[i][j] = dp[i - 1][j - v[i]] + w[i];
}
printf("%d", dp[n][vi]);
return 0;
一维写法
代码
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int dp[1005];
int main()
{
int n, vi, v[1005], w[1005];
scanf("%d%d", &n, &vi);
for (int i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
for(int i=1;i<=n;i++)
for (int j =vi; j >= v[i]; j--)//j从大到小
{
if (dp[j] <= (dp[j - v[i]] + w[i]))
dp[j] = dp[j - v[i]] + w[i];
}
printf("%d", dp[vi]);
return 0;
}