#include<iostream> #include<algorithm> using namespace std; int w[21]={0}; int v[21]={0}; int flag[21]={0}; int arr[21][1024]={0}; int main() { int n=0,c=0; scanf("%d%d",&n,&c); for(int i=1;i<=n;i++) { scanf("%d",&w[i]); } for(int i=1;i<=n;i++) { scanf("%d",&v[i]); } for(int i=1;i<=n;i++)//物品i { for(int j=1;j<=c;j++)//重量j { if(j>=w[i]) { arr[i][j]=max(arr[i-1][j],arr[i-1][j-w[i]]+v[i]); } else arr[i][j]=arr[i-1][j]; } } printf("%d ",arr[n][c]); int h=n,g=c; while(h>=1) { if(arr[h][g]==arr[h-1][g])flag[h]=0; else { flag[h]=1; g=g-w[h]; } h--; } for(int i=1;i<=n;i++) { printf("%d",flag[i]); } return 0; }

这是一个背包问题的动态规划解法。输入包括两个整数 n 和 c，表示物品数量和背包容量。接下来输入 n 个物品的重量和价值。程序使用一个二维数组 arr 存储每个物品在不同的重量下的最大价值。最后输出 arr[n][c] 即为背包能够容纳的最大价值。

接着程序使用一个数组 flag 存储是否选择了该物品。从 arr[n][c] 开始，倒序遍历 arr 数组，根据递推公式 arr[i][j]=max(arr[i-1][j],arr[i-1][j-w[i]]+v[i]) 判断是否选择了物品 i，如果选择了，则 flag[i] 为 1，否则为 0。最后输出 flag 数组即为物品的选择情况。

相关问题

#include <iostream> #include <vector> #include <string> #include <algorithm> #include <map> #include <thread> #include "List.h" #include "Node.h" using namespace std; int main(void) { auto* head = new Node<int>(10); //auto *list = new List<int>(head); List<int> list(head); //list->Display(); return 0; }

这段代码包含了 List 类和 Node 类的头文件，并且定义了一个 main 函数。在 main 函数中，它首先创建了一个 Node 对象 head，数据值为 10。然后，它使用 head 对象创建了一个 List 对象 list。最后，它调用了 List 类的成员函数 Display 输出链表中的元素。

需要注意的是，由于 List 类已经包含了头节点指针 _head 和链表长度 _size，因此没有必要再使用指针变量 list 来引用 List 对象。因此，可以直接使用 List<int> list(head) 来创建对象。另外，注释掉的 list->Display() 可以直接通过 list.Display() 来调用，因为 Display 函数是一个公有成员函数。

#include <iostream> #include <string> #include <cmath> #include <iomanip> #include <algorithm> #include <conio.h> using namespace std; void test(int *A[]) {for(int a=0;a<2;a++) {cout<<A[a]<<endl; } } int main() {int *a[2]={0}; int b=3; a[1]=&b; test(a); }这段代码为什么不输出0 3

这段代码不会输出0 3，而是会输出一个地址和3。

在函数test中，传入的参数A是一个数组指针，类型为int *A[]。在主函数中定义了一个数组指针a，类型也为int *a[]。在主函数中，a[1]=&b;表示将变量b的地址赋给了数组指针a的第二个元素。因此，当调用test(a)时，test函数中的循环会打印出数组指针中的两个元素，即a[0]和a[1]所指向的地址。

由于在主函数中，a数组指针的第一个元素a[0]没有被初始化，因此它的值为0。而a数组指针的第二个元素a[1]被赋值为变量b的地址，因此它的值为b的地址，而不是3。因此，test函数中打印的结果是一个地址和3，而不是0和3。