编程题目求思路

渣银选手来答一发。这题有一个分组背包的思路，请看下面的表： . . . . . ... ... ... 假设答案为 那么它等价于 相信聪明的你已经发现了，如果答案存在，则存在从上面的表的每一列选择一个数字，它们的和为 0。所以这就变成了一个简单的分组背包的问题了。当然实现时需要避开一个小bug，也就是上面的表全选0的情况，还有，统计和的时候也得想想办法。anyway，这是我的代码： # include <bits/stdc++.h> using namespace std; const int N = 100 + 5; const int M = 2000 + 5; bool dp[N][3][M * 4]; //dp[i][0/1/2][j] = (0/1) 表示前i个里面(0: 选择+a[i] 1: 选择-a[i] 2: 不选第i个数字)之后是否能凑成总和j int sum[N][3][M * 4]; //记录一下路径上正数的和，便于统计答案 int a[N]; int f(int x) //因为可能出现负数下标，所以做这个处理 { return x + 4000; } int main () { int n; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; dp[0][2][f(0)] = true; for (int i = 0; i < n; ++i) { for (int j = 0; j <= 2; ++j) { for (int k = f(-2000); k <= f(2000); ++k) { if (dp[i][j][k] == false) continue; dp[i+1][0][k + a[i+1]] = true; sum[i+1][0][k + a[i+1]] = max(sum[i+1][0][k + a[i+1]], sum[i][j][k] + a[i+1]); dp[i+1][1][k - a[i+1]] = true; sum[i+1][1][k - a[i+1]] = max(sum[i+1][1][k - a[i+1]], sum[i][j][k]); dp[i+1][2][k] = true; sum[i+1][2][k] = max(sum[i+1][2][k], sum[i][j][k]); } } } for (int i = 0; i <= 2; ++i) { if (dp[n][i][f(0)] == true && sum[n][i][f(0)] != 0) { // 之所以 sum[n][i][f(0)] != 0 是为了排除全都不选的特殊情况 cout << sum[n][i][f(0)]; return 0; } } cout << "Impossible" << endl; return 0; } 看懂点个赞哈~

这个可以不全用很骚啊...

测了几个样例，不知道对不对 //f[i][j]表示考虑前i个物品，两个背包的差值为j的情况下的最大重量和 //ans=f[n][0]/2 (即求出来的是最大的可能) #include <bits/stdc++.h> using namespace std; int f[105][2005]; int w[105]; int main() { int n; cin>>n; for (int i=1; i<=n; i++) cin>>w[i]; memset(f,-1,sizeof(f)); f[0][0]=0; for (int i=1; i<=n; i++) { for (int j=0; j<=2000; j++) { if (f[i-1][j]!=-1) { f[i][j]=max(f[i][j],f[i-1][j]); if (w[i]>j) f[i][w[i]-j]=max(f[i][w[i]-j], f[i-1][j]+w[i]); else f[i][j-w[i]]=max(f[i][j-w[i]],f[i-1][j]+w[i]); f[i][j+w[i]]=max(f[i][j+w[i]],f[i-1][j]+w[i]); } } } if (f[n][0]>0) cout<<f[n][0]/2<<endl; else cout<<"Impossible"<<endl; return 0; }

这个不止一种分法吧，如果存在多种情况，怎么输出，比如你这题 6也是结果啊

用2 4和1 5不行吗。为啥结果只有7