首页 > 代码库 > HDU 2602
HDU 2602
//突然发现怎么让字体变色了..这样看着比较舒服..
1 //01背包入门(一维数组)
2 1.#include<iostream>
3 2.#define maxn 1005
4 3.using namespace std;
5 4.int v[maxn],w[maxn],dp[maxn];
6 5.int max(int a,int b)
7 6.{
8 7. return a>b?a:b;
9 8.}
10 9.int main()
11 10.{
12 11. //freopen("1002.txt","r",stdin);
13 12. int t,n,m,i,j;
14 13. while(~scanf("%d",&t))
15 14. {
16 15. while(t--)
17 16. {
18 17. memset(v,0,sizeof(v));
19 18. memset(w,0,sizeof(w));
20 19. memset(dp,0,sizeof(dp));
21 20. scanf("%d%d",&n,&m);
22 21. for(i=0;i<n;i++)
23 22. scanf("%d",w+i);
24 23. for(i=0;i<n;i++)
25 24. scanf("%d",v+i);
26 25. for(i=0;i<n;i++)
27 26. for(j=m;j>=v[i];j--) //j表示当前背包剩余容量
28 27. dp[j]=max(dp[j],dp[j-v[i]]+w[i]); //dp[j-v[i]+w[i]]代表装入第i件物品
29 28. printf("%d\n",dp[m]);
30 29. }
31 30.
32 31. }
33 32. return 0;
34 33.}
2 1.#include<iostream>
3 2.#define maxn 1005
4 3.using namespace std;
5 4.int v[maxn],w[maxn],dp[maxn];
6 5.int max(int a,int b)
7 6.{
8 7. return a>b?a:b;
9 8.}
10 9.int main()
11 10.{
12 11. //freopen("1002.txt","r",stdin);
13 12. int t,n,m,i,j;
14 13. while(~scanf("%d",&t))
15 14. {
16 15. while(t--)
17 16. {
18 17. memset(v,0,sizeof(v));
19 18. memset(w,0,sizeof(w));
20 19. memset(dp,0,sizeof(dp));
21 20. scanf("%d%d",&n,&m);
22 21. for(i=0;i<n;i++)
23 22. scanf("%d",w+i);
24 23. for(i=0;i<n;i++)
25 24. scanf("%d",v+i);
26 25. for(i=0;i<n;i++)
27 26. for(j=m;j>=v[i];j--) //j表示当前背包剩余容量
28 27. dp[j]=max(dp[j],dp[j-v[i]]+w[i]); //dp[j-v[i]+w[i]]代表装入第i件物品
29 28. printf("%d\n",dp[m]);
30 29. }
31 30.
32 31. }
33 32. return 0;
34 33.}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。