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