|
|
板凳
楼主 |
发表于 2018-9-19 13:18:27
|
只看该作者
以上都是简单的背包问题，我们用的填表大法，二维数组比较直观，但是有点浪费，其实也可以一维数组，那么就是本地迭代。在此之前，请认真体会fibo数列，辗转相除求最大公约数，杨辉三角的一维数组做法。
请看第一题，1,3,4,7,8的砝码各一个，能不能拼出10克的重量，我们用一维数组bi表示i克能否拼出，那么初始的时候，全部是0.
b0=1，
先来一个1克的砝码b1=1
再来一个3克的 因为b0=b1=1，所以b(0+3)=b(1+3)=1
再来一个4克的。因为b0=b1=b3=b4=1所以 b(0+4)=b(1+4)=b(3+4)=b(4+4)=1
**
就是说从每来一个砝码，就把这个所有的为1的重量的加上这个砝码的重量设为1为了避免重复累加，应该类似杨辉三角，从后往前推。（！！！！！）
代码如下：
- #include <iostream>
- using namespace std;
- int a[]= {0,1,3,4,7,8};
- bool f[30];///表示能否凑出
- int x,i,j;
- int main()
- {
- f[0]=1;
- for (i=1; i<=5; i++) ///枚举5个砝码
- {
- for(j=29; j>=a[i]; j--) ///由后向前
- f[j]=f[j]||f[j-a[i]]; ///或者我可以 ，或者j-a[i]可以
- }
- for(j=0; j<=29; j++) cout<<f[j]<<' ';
- return 0;
- }
第四题是标准的背包问题，用一维数组的解法如下，和前面有点不同的地方是这个判断标准，上面用的是或者运算，这里用的是求最大值的运算- #include <iostream>
- using namespace std;
- int w[]= {0,1,3,4,7,8};
- int v[]= {0,10,25,35,80,100};
- int f[30];
- int x,i,j;
- bool t1,t2;
- int main()
- {
-
- for (i=1; i<=5; i++) ///枚举5个砝码
- {
- for(j=29; j>=w[i]; j--) ///由后向前
- f[j]=max(f[j],f[j-w[i]]+v[i]); ///或者我可以 ，或者j-a[i]可以
- }
- for(j=0; j<=29; j++) cout<<f[j]<<' ';
- return 0;
- }
|
|
发表于 2018-9-8 22:08:52
收藏
