参考代码:
#include <iostream> using namespace std; const int N = 110, M = 300000;//大一点好 int n,sum,w[N]; int f[N][M]; int main() { cin >> n; for (int i = 1;i <= n; i++) { cin >> w[i]; sum += w[i]; } f[0][0]=1; for(int i = 1; i <= n; i++) { for(int j = 0; j <= sum; j++) { //1、f[i-1][j]意味着不选第i个就可以达到重量j //2、f[i-1][j+w[i]]意味着第i个将放在另一边抵消w[i]达到j //3、f[i-1][abs(j-w[i])]意味着用第i个补上w[i]达到j f[i][j] = f[i - 1][j] || f[i - 1][j + w[i]] || f[i - 1][abs(j - w[i])]; } } int ans = 0; for(int i = 1; i <= sum; i++) //0不可能,故从1开始遍历 if(f[n][i]) ans++; cout << ans; return 0; }
0.0分
5 人评分