有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
#include<iostream> #include<vector> using namespace std; int max(int a, int b) { return a > b ? a : b; } /*二维数组方式*/ /* 1、每个cap+1长度的数组，记录的是在前i个物品可选的情况下，每个体积下的最大价值 2、放入第i+1个物品时，除了状态转移，还要注意对上一状态的复制 */ int bag1(int w[], int value[], int n, int cap) { int **mat = new int*[n+1]; //建立二维数组，其实是一个指针数组 for (int i = 0; i <= n; i++) //指针指向一个一维数组 { mat[i] = new int[cap + 1]; memset(mat[i], 0, (cap+1)*4); //memset使用格式 } for (int i = 0; i < n; i++) { for (int j = 0; j <= cap; j++) //一定记住从0开始 { if (j >= w[i]) //保留等号 mat[i + 1][j] = max(mat[i][j], mat[i][j - (w[i])] + value[i]); else //不满足时，要复制 mat[i + 1][j] = mat[i][j]; } } return mat[n][cap]; } /* 一维数组方式 */ int bag2(int w[], int value[], int n, int cap) { int *dp = new int[cap+1]; memset(dp, 0, (cap + 1)*sizeof(int)); for (int i = 0; i < n; i++) { for (int j = cap; j>0; j--) { if (j >= w[i]) dp[j] = max(dp[j], dp[j - (w[i])] + value[i]); } } return dp[cap]; } int main() { int w[] = { 2,3,5,7 }; int value[] = { 1,5,2,4}; cout << bag1(w, value, 4, 10) << endl; cout << bag2(w, value, 4, 10) << endl; system("pause"); return 0; }