题目链接：https://vjudge.net/contest/103424
题目大意：
第一行输入几组数据，第二行第一个数字代表物体个数，第二个数代表总体积。需要注意的是，第三排输入的是物品的价值，第四排的物品的体积。在不可以拆分物体的前提下，已知背包的总体积，最大能获取的价值是多少。
01背包模板题，没什么好说的。(附两种形式的dp数组解决方案)
//一维dp数组实现（滚动数组）
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))int main()
{
int t, n, m, i, j;
int a[], b[];
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
for (i = ; i<n; i++)
scanf("%d", &a[i]);
for (i = ; i<n; i++)
scanf("%d", &b[i]);
int dp[]; //dp数组始终记录当前体积的最大价值
memset(dp, , sizeof(dp));
for (i = ; i<n; i++) //从第一个开始循环
for (j = m; j >= b[i]; j--)
dp[j] = max(dp[j], dp[j - b[i]] + a[i]); //比较放入i物体后的价值与不放之前的价值，记录大的值
printf("%d\n", dp[m]); //输入总体积的最大价值
}
return ;
}
//二维dp数组实现
#include<iostream>
using namespace std;
int dp[][]; //dp[i][j]表示前i个物品，当背包容量为j的时候所能装下大的最大值
#define max(a,b) ((a)>(b)?(a):(b))int main()
{
int t, n, v, i, j;
int va[], vo[];
cin >> t;
while (t--)
{
cin >> n >> v;
for (i = ; i <= n; i++)
cin >> va[i];
for (i = ; i <= n; i++)
cin >> vo[i];
memset(dp, , sizeof(dp));//初始化操作
for (i = ; i <= n; i++)
{
for (j = ; j <= v; j++)
{
if (vo[i] <= j)//表示第i个物品将放入大小为j的背包中
dp[i][j] = max(dp[i - ][j], dp[i - ][j - vo[i]] + va[i]); //比较放入i物体后的价值与不放之前的价值，记录大的价值
else //第i个物品无法放入
dp[i][j] = dp[i - ][j];
}
}
cout << dp[n][v] << endl;
}
return ;
}
2018-04-27
