大家来看看我用C++写01背包程序
1、先看题目
(1)题目描述
有1个容量为m的背包,现有n种物品,重量分别为w1,w2…wn,价值分别为v1,v….vn,若每种物品只有1件,求能放入的最大总价值。
(2)输入描述
第1行,两个整数m(m<=200)和n(n<=30)。
第2行到最后,每行两个整数wi和vi
(3)输出描述
一个数据,最大总价值
(4)样例输入
20 7
2 1
3 3
4 5
7 9
5 7
1 3
1 9
(5)样例输出
34
2、正确代码
1 #include<iostream>
2 using namespace std;
3
4 int main(){
5 int N;
6 int W;
7 int w[30]={0};
8 int v[30]={0};
9 int k,C;
10 int p;
11 int B[30][200] = {0};
12 cin>>W>>N;
13 for(p=1;p<N+1;p++){
14 cin>>w[p] >>v[p];
15 }
16 for(k=1;k<N+1;k++){
17 for(C = 1;C < W+1;C++){
18 if(w[k] > C){
19 B[k][C] = B[k-1][C];
20 }
21 else{
22 int value1 = B[k-1][C-w[k]] + v[k];
23 int value2 = B[k-1][C];
24 if(value1 > value2){
25 B[k][C] = value1;
26 }
27 else{
28 B[k][C] = value2;
29 }
30 }
31 }
32 }
33 cout<<B[N][W ]<<endl;
34 return 0;
35 }
3、验证
使用DEV c++ 运行
(1)完成样例输入
(2)完成样例输出
结束End
原文链接: https://www.cnblogs.com/wrt2022/p/TheDevc-plus-plus-01knapsack_me-and-According-to-the-original.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/186867
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!