不使用第一个dim，直接用1dim的dp数组来做的，是0-1背包问题的，做了些改动的，主要是多了附件，若是没有附件的话，就是标准的0-1背包问题的；附件的处理是最重要的，用map记录了附件，通过map可以直接查询出每个主件包括的所有附件在0-1背包的基础上，需要在第二层循环，加入附件的，然后看加入附件以后的收益，和之前的收益，拿到最大值就可以 #include<iostream> #include<vector> #include<unordered_map> #include<algorithm> using namespace std; in...

#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(void) { // 0-1背包问题的，dp是目标函数，也就是体积是j的最大收益，物体体积已经给出了，要让剩下的体积最小，那么就是使用的体积最大 // 只需要让收益是体积就可以，若收益最大那么占用的体积最大的 // 也就是是否选择这件物体，不选择就是dp[i-1][j]，i-1件物品占用j体积的最大收益，选择以后就是dp[i-1][j-num[i]] + num[i]，i-1件物品占用j-...

#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(void) { // 0-1背包问题的，可以划分到两个和相等的数组，那么背包的体积就是所有数的和的一半 sum/2，而且和不能被2整除就是false // 那么就是选择若干个数，使得占满背包的体积，物体是每个数字，物体的体积就是数字本身，收益可以人工指定1或者其他数字 int i, j, k, m, n, x, y = 0, z = -6, aim, sum = 0, hal; cin&g...

#include<iostream> #include<vector> using namespace std; int main(void){ /* 看作完全背包问题，aim是背包的容量，n是物体的个数，-1是物体默认的收益，最大化装满以后背包的收益，-1的绝对值就是物体的个数，所以就是最小化物体的个数 */ int i, j, k, m, n, x, y = 0, z = 0, aim; cin>>n>>aim; vector<int> arr(n), dp(aim+1, -0xfffffff); for(i = 0; i &lt...

#include<iostream> #include<vector> #include<algorithm> #include<cmath> using namespace std; struct nod { int vi; int wi; }; int power[106]; void getpower() { for(int i = 0; i < 106; i++) { //求出每个物体的体积 power[i] = i * i; } } vector<int> dp(10006, -0xfffffff); // dp数组初...

#include<iostream> #include<vector> #include<algorithm> using namespace std; struct nod { int vi; int wi; }; int main(void) { int i, j, k, n, m, maxmax, V; cin>>n>>V; vector<nod> t(n); vector<int> dp(V+1, 0); // 装满的话就是dp数组的背包容量值>0，若背包容量<0，则装不满的呢 fill(d...

#include<iostream> #include<vector> #include<algorithm> using namespace std; struct nod { int vi; int wi; }; int main(void) { int i, j, k, n, m, maxmax, V; cin>>n>>V; vector<nod> t(n); vector<int> dp(V+1, 0); // 装满的话就是dp数组的背包容量值>0，若背包容量<0，则装不满的呢 fill(d...

#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(void) { int i, j, k, n, m, maxmax = -999999999, cnt, x, y, z; cin>>n; vector<int> t(n); for(i = 0; i < n; i++) scanf("%d", &t[i]); vector<int> f(t), pt(n, 0), ng...