解题思路:当我看到这题的第一眼立马就想到了dfs在没有使用记忆化搜索是只拿了45分,于是开始了dp,在看了一些大佬的讲解后,明白了这个01背包的变种问题,
我们把题目看成这样,有一个容量为max(砝码总重量)的背包,每个砝码就是一件商品,你要做的不是选出价值最大的选法,而是去探讨选任意多砝码看看能剩下多少空间,话已至此,请自己想想看吧
注意事项:减去重量时要加绝对值
参考代码:
#include<stdio.h>
#include<math.h>
int w[1000],dp[1000][10000],ans;
int main(){
int n,sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
sum+=w[i];
}
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=sum;j>=0;j--){
dp[i][j]=dp[i-1][j]||dp[i-1][abs(j-w[i])]||dp[i-1][abs(j+w[i])];
}
}
for(int i=1;i<=sum;i++){
if(dp[n][i]==1){
ans++;
}
}
printf("%d",ans);
return 0;
}
0.0分
3 人评分
C语言训练-排序问题<2> (C++代码)浏览:929 |
矩阵乘法 (C++代码)浏览:1652 |
A+B for Input-Output Practice (II) (C语言代码)浏览:1038 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:1214 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:909 |
WU-蓝桥杯算法提高VIP-勾股数 (C++代码)浏览:1678 |
众数问题 (C语言代码)浏览:898 |
WU-输入输出格式练习 (C++代码)浏览:1124 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:911 |
a+b浏览:451 |