题目链接：https://vjudge.net/contest/125308#problem/M
题意：有N件物品和一个容量为V的背包。第i件物品的费用是体积c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。简单的01背包问题主要是状态转移式
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}，即可求解：
AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[];
struct Node
{
int volume;
int value;
} a[];
int main()
{
int t1,i, j, t, m;
scanf("%d",&t1);
while(t1--)
{
scanf("%d%d", &t, &m);
memset(dp,,sizeof(dp));
for (i = ; i <= t; i++)
scanf("%d",&a[i].value);
for(i = ; i <= t; i ++)
scanf("%d",&a[i].volume);
for (i = ; i <= t; i++)
{
for (j = m; j >= a[i].volume; j--)
{
dp[j] = max(dp[j], dp[j - a[i].volume] + a[i].value);
}
}
printf("%d\n", dp[m]);
}
return ;
}
FAQ | About | Google Group | Discuss | Github | Author
All Copyright Reserved ©- HUST ACM/ICPC TEAM