0-1背包问题 c语言_动态编程在C中的0-1背包问题
0-1背包问题 c语言
Here you will learn about 0-1 knapsack problem in C.
在这里，您将学习C语言中的0-1背包问题。
We are given n items with some weights and corresponding values and a knapsack of capacity W. The items should be placed in the knapsack in such a way that the total value is maximum and total weight should be less than knapsack capacity.
我们给了n个具有一定权重和相应值的项目以及一个容量为W的背包。这些项目应以总值最大且总重量小于背包容量的方式放置在背包中。
In this problem 0-1 means that we can’t put the items in fraction. Either put the complete item or ignore it. Below is the solution for this problem in C using dynamic programming.
在这个问题0-1中，意味着我们不能将项目分成零。 放入完整的项目或忽略它。 下面是使用动态编程在C中解决此问题的方法。
动态编程的C背包问题程序 (
Program for Knapsack Problem in C Using Dynamic Programming)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include<stdio.h>
int max(int a, int b) { return (a > b)? a : b; }
int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n+1][W+1];
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
int main()
{
int i, n, val[20], wt[20], W;
printf("Enter number of items:");
scanf("%d", &n);
printf("Enter value and weight of items:\n");
for(i = 0;i < n; ++i){
scanf("%d%d", &val[i], &wt[i]);
}
printf("Enter size of knapsack:");
scanf("%d", &W);
printf("%d", knapSack(W, wt, val, n));
return 0;
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include<stdio.h>
int max ( int a , int b ) { return ( a > b ) ? a : b ; }
int knapSack ( int W , int wt [ ] , int val [ ] , int n )
{
int i , w ;
int K [ n + 1 ] [ W + 1 ] ;
for ( i = 0 ; i <= n ; i ++ )
{
for ( w = 0 ; w <= W ; w ++ )
{
if ( i == 0 || w == 0 )
K [ i ] [ w ] = 0 ;
else if ( wt [ i - 1 ] <= w )
K [ i ] [ w ] = max ( val [ i - 1 ] + K [ i - 1 ] [ w - wt [ i - 1 ] ] , K [ i - 1 ] [ w ] ) ;
else
K [ i ] [ w ] = K [ i - 1 ] [ w ] ;
}
}
return K [ n ] [ W ] ;
}
int main ( )
{
int i , n , val [ 20 ] , wt [ 20 ] , W ;
printf ( "Enter number of items:" ) ;
scanf ( "%d" , & n ) ;
printf ( "Enter value and weight of items:\n" ) ;
for ( i = 0 ; i < n ; ++ i ) {
scanf ( "%d%d" , & val [ i ] , & wt [ i ] ) ;
}
printf ( "Enter size of knapsack:" ) ;
scanf ( "%d" , & W ) ;
printf ( "%d" , knapSack ( W , wt , val , n ) ) ;
return 0 ;
}
|
Output
输出量
Enter number of items:3 Enter value and weight of items: 100 20 50 10 150 30 Enter size of knapsack:50 250
输入物品数量：3 输入物品的重量和重量： 100 20 50 10 150 30 输入背包尺寸：50 250
You can watch below video to learn knapsack problem easily.
您可以观看下面的视频轻松了解背包问题。
Source: http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/
资料来源： http : //www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/
翻译自: https://www.thecrazyprogrammer.com/2016/10/knapsack-problem-c-using-dynamic-programming.html
0-1背包问题 c语言