简单的背包问题 描述 小冯有个存储重量为m的空间存储袋，现在有n件物品，每件物品的重量为w，价值为v。问小冯最多能装的最大价值为多少？输入 第一行输入两个数m、n，（1<=n,m<=1000）n表示物品数量，m表示存储袋的最大重量;接下来的n行，每行输出w,v,(1<=w,v <= 100)分别表示物品的重量，物品的价值; 输出 输出小冯能装的物品最大价值; 样例输入 70 371 10069 11 2 样例输出 3题解 利用动态空间规划可以建立一个二维数组存储物品价值，行为物品个数，列为重量比较和比这个物品重量小的物品的价值的和，和上一个物品价值的值哪个大否则返回上一个物品的价值个数/重量01230000010000200003000040000放入第一个物品重量为1，价值为2个数/重量01230000010222200003000040000放入第二个物品重量为2，价值为4个数/重量01230000010222202463000040000代码实例#include<iostream> #include<cstdlib> using namespace std; int m, n, i, j; int w[1000], c[1000], f[1000][1000]; int main() { cin >> m >> n;//m代表背包最大能装的重量，n代表物品的数量 for (i = 1; i <= n; i++) { cin >> w[i] >> c[i];//输入每个物品的重量和价值 } //i控制物品，j控制重量 for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { if (j >= w[i]) { f[i][j] = max(f[i - 1][j - w[i]] + c[i], f[i - 1][j]); } else{ f[i][j] = f[i - 1][j]; } } } cout << f[n][m] << endl; return 0; }vector版：#include<iostream> #include<vector> #include<cstdlib> using namespace std; int n, w, i, j; int main() { cin >> w >> n; //定义容器行为几号物品，列为重量 vector<vector<int>>f(n + 1, vector<int>(w+1,0)); //定义重量与价值的容器 vector<int>weight(n +1); vector<int>price(n + 1); //输入 for ( i = 1; i <= n; i++) { cin >> weight[i] >> price[i]; } for (i = 1; i <= n; i++) { for (j = 1; j <= w; j++) { if (j >= weight[i]) { f[i][j] = max(f[i - 1][j - weight[i]] + price[i], f[i - 1][j]);//比较和比这个物品重量小的物品的价值的和，和上一个物品价值的值哪个大 } else { f[i][j] = f[i - 1][j];//否则返回上一个物品的价值 } } } cout << f[n][w] << "\n"; return 0; }

二进制，八进制，十进制，十六进制之间的互相转换 二进制 由“01”组成。逢2进1。 八进制 由“01234567”组成。逢8进1。一般由0开头 十进制 由“0123456789”组成。逢10进1。 十六进制 由“0123456789ABCDEF”。逢16进1。一般由0x开头十进制转换二进制，八进制，十六进制 设X为十进制数，Y为二，八，十六进制数。 由除法运算可知有整数Z和余数D 式子结构如：X/Y==Z... ...D 转换规则为用X除Y取余，再用Z除Y取余，，，重复操作直至Z无法再除 十进制转换二进制例子： 如：将十进制52转换为二进制数 52/2==26... ... 0 ---> 0 取余，将0放至最右边保留 26/2==13... ... 0 ---> 00 13/2==6 ... ... 1 ---> 100 6/2==3 ... ... 0 ---> 0100 3/2==1 ... ... 1 ---> 10100 1/2==0 ... ... 1 --->110100十进制转换八进制例子： 如：将575转换为八进制数 575/8==71... ... 7 ---> 7 操作与二进制一样 71/8== 8... ... 7 ---> 77 8/8== 1... ... 0 ---> 077 1/8== 0... ... 1 ---> 1077十六进制同理便不再赘述 十进制转N进制代码实例#include<iostream> #include<string> using namespace std; #define N 2//示例为十进制转换二进制，其他进制需要把2修改 string conversion(int num_10) { if (num_10 == 0) { string str = "0"; return str; } string temp = ""; string num_N = "01";//示例为十进制转换二进制，因此在""内为01，若为八进制则改为01234567 int i; for (i = 0; num_10 != 0; i++) { temp = num_N[num_10 % N] + temp; num_10 /= N; } return temp; } int main() { int num_10; string num_N; cin >> num_10; num_N=conversion(num_10); cout << num_N << endl; return 0; }N进制转换十进制 利用数的位权计算二进制数1111转换十进制过程如下12^3+12^2+1 2^1+12^0==15八进制数17转换十进制过程如下1 8^1+78^0==15十六进制同理便不再赘述 N进制转十进制代码实例//N进制转十进制 #include<iostream> #include<string> #include<cmath> using namespace std; #define N 2//示例为二进制转换十进制 int conversion(string num_N) { int i; int size = num_N.size(); int num=0,temp=0; for (i = 0; i < size; i++) { temp = num_N[i] - '0'; num = num + temp * pow(N, size - i - 1); } return num; } int main() { string num_N; int num_10; cin >> num_N; num_10 = conversion(num_N); cout << num_10 << endl; return 0; }以上两个为十进制转换N进制和N进制转换十进制当需要十六进制，八进制，二进制之间的转换可以先转换十进制，再转换进制