backpack

深藏阁楼爱情的钟 2022-01-10 01:15 135阅读 0赞

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 ****** 0-1 背包******
      2 Int main()
      3 {
      4     //0-1背包
      5     n，V//个数，体积
      6     1<<i<<n v[i]//体积
      7     1<<i<<n w[i]//价值
      8     memset(dp,0,sizeof(dp));
      9     for(int i=1;i<=n;i++){
     10 
     11         for(int j=0;j<=V；j++){
     12             dp[i][j]=dp[i-1][j];
     13         }
     14         for(int j=0;j+v[i]<=V;j++){
     15             dp[i][j+v[i]]=max(dp[i][j+v[i]],dp[i-1][j]+w[i]);
     16         }
     17         //或者
     18         /*for(int j=v[i];j<=V;j++){
     19             dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
     20         }*/
     21 
     22         /*for(int j=1;j<=V;j++){
     23             printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
     24         }
     25         */
     26     }
     27     int result =0;
     28     for(int i=1;i<=V;i++){
     29         if(dp[n][i]>result){
     30             result=dp[n][i];
     31         }
     32     }
     33 
     34     //节省空间
     35 
     36     memset(dp,0,sizeof("dp"));
     37     for(int i=1;i<=n;i++){
     38         for(j=V-v[i];j>=0;j--){
     39             dp[j+v[i]]=max(dp[j+v[i]],dp[j]+w[i]);
     40         }
     41 
     42         /*
     43         for(j=1;j<=V;j++){
     44             printf("dp[%d]=%d\n",j,dp[j]);
     45         }
     46         */
     47     }
     48     int result=0;
     49     for(int i=1;i<=V;i++){
     50         if(dp[i]>result){
     51             result=dp[i];
     52         }
     53     }
     54 }
     55 
     56 
     57 求体积最jiejing W。
     58 int main
     59 {
     60     memset(dp,0,sizeof(dp));
     61     dp[0]=1;
     62     for(int i=1;i<=n;i++)
     63     {
     64         for(int j=W-v[i];j>=0;j--)
     65         {
     66             if(dp[j]==1)
     67             {
     68                 dp[j+v[i]]=1;
     69             }
     70         }
     71     }
     72     int result=0,i;
     73     for(i=W;i>=0;i++)
     74     {
     75         if(dp[i]==1)
     76         {
     77             result=dp[i];
     78             break;
     79         }
     80     }
     81 }
     82 *******多重背包*******
     83 #include<stdio.h>
     84 #include<string.h>
     85 int main()
     86 {
     87     int cash,N,n[15],v[15],i,j;
     88     int dp[100005],Time[100005];//计数器
     89 
     90     while(scanf("%d %d",&cash,&N)!=EOF)
     91     {
     92 
     93     for(i=1;i<=N;i++)
     94         scanf("%d %d",&n[i],&v[i]);
     95     memset(dp,0,sizeof(dp));
     96     for(i=1;i<=N;i++)
     97     {
     98         memset(Time,0,sizeof(Time));//计数器清零
     99         for(j=v[i];j<=cash;j++)
    100         {
    101             if(dp[j]<dp[j-v[i]]+v[i] && Time[j-v[i]]<n[i])
    102             {
    103                 dp[j]=dp[j-v[i]]+v[i];
    104                 Time[j]=Time[j-v[i]]+1;//+1
    105             }
    106         }
    107     }
    108     printf("%d\n",dp[cash]);
    109 
    110     }
    111     return 0;
    112 }

Charm Bracelet

**Time Limit:**1000MS     **Memory Limit:**65536KB     **64bit IO Format:**%I64d & %I64u

[Submit][]  [Status][]  [Practice][]  [POJ 3624][]

Description

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the *N* (1 ≤ *N* ≤ 3,402) available charms. Each charm *i* in the supplied list has a weight *Wi* (1 ≤ *Wi* ≤ 400), a 'desirability' factor *Di* (1 ≤ *Di* ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than *M* (1 ≤ *M* ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

Input

\* Line 1: Two space-separated integers: *N* and *M*  
\* Lines 2..*N*\+1: Line *i*\+1 describes charm *i* with two space-separated integers: *Wi* and *Di*

Output

\* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

Sample Input

4 6
    1 4
    2 6
    3 12
    2 7

Sample Output

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<algorithm>
     4 using namespace std;
     5 
     6 int main()
     7 {
     8     int i,j,k,N,M;
     9     int v[3505],w[3505],dp[12888];
    10     while(scanf("%d %d",&N,&M)!=EOF)
    11     {
    12         for(i=1;i<=N;i++)
    13         {
    14             scanf("%d %d",&v[i],&w[i]);
    15         }
    16 
    17         memset(dp,0,sizeof(dp));
    18         for(i=1;i<=N;i++)
    19         {
    20             for(j=M-v[i];j>=0;j--)
    21             {
    22                 dp[j+v[i]]=max(dp[j+v[i]],dp[j]+w[i]);
    23             }
    24         }
    25 
    26         int ans=0;
    27         for(i=1;i<=M;i++)
    28         {
    29             if(dp[i]>ans)
    30                 ans=dp[i];
    31         }
    32         printf("%d\n",ans);
    33     }
    34     return 0;
    35 }

TWO

Bookshelf 2

**Time Limit:**1000MS     **Memory Limit:**65536KB     **64bit IO Format:**%I64d & %I64u

[Submit][]  [Status][Status 1]  [Practice][Practice 1]  [POJ 3628][]

Description

Farmer John recently bought another bookshelf for the cow library, but the shelf is getting filled up quite quickly, and now the only available space is at the top.

FJ has *N* cows (1 ≤ *N* ≤ 20) each with some height of *Hi* (1 ≤ *Hi* ≤ 1,000,000 - these are very tall cows). The bookshelf has a height of *B* (1 ≤ *B* ≤ *S*, where *S* is the sum of the heights of all cows).

To reach the top of the bookshelf, one or more of the cows can stand on top of each other in a stack, so that their total height is the sum of each of their individual heights. This total height must be no less than the height of the bookshelf in order for the cows to reach the top.

Since a taller stack of cows than necessary can be dangerous, your job is to find the set of cows that produces a stack of the smallest height possible such that the stack can reach the bookshelf. Your program should print the minimal 'excess' height between the optimal stack of cows and the bookshelf.

Input

\* Line 1: Two space-separated integers: *N* and *B*  
\* Lines 2..*N*\+1: Line *i*\+1 contains a single integer: *Hi*

Output

\* Line 1: A single integer representing the (non-negative) difference between the total height of the optimal set of cows and the height of the shelf.

Sample Input

5 16
    3
    1
    3
    5
    6

Sample Output

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 
     4 int dp[20000001];
     5 int main()
     6 {
     7     int N,B,i,j,result,s;
     8     int H[25];
     9     while(scanf("%d %d",&N,&B)!=EOF)
    10     {
    11         s=0;
    12         for(i=1;i<=N;i++)
    13         {
    14             scanf("%d",&H[i]);
    15             s=s+H[i];
    16         }
    17         for(i=0;i<=s;i++)
    18             dp[i]=0;
    19         dp[0]=1;
    20         for(i=1;i<=N;i++)
    21         for(j=s-H[i];j>=0;j--)    
    22         {
    23             if(dp[j]==1)
    24                 dp[j+H[i]]=1;
    25         }
    26         result=0;
    27         for(j=B;j<=s;j++)
    28             if(dp[j]==1)
    29             {
    30                 result=j-B;
    31                 break;
    32             }
    33         printf("%d\n",result);
    34     } 
    35     return 0;
    36 }

转载于:https://www.cnblogs.com/cyd308/p/4520607.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/2e158f67ed344bd38c66dd82b71f44ef.png
[Submit]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=69281
[Status]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=69281#status//A/0
[Practice]: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17547
[POJ 3624]: http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17547
[Status 1]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=69281#status//B/0
[Practice 1]: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17747
[POJ 3628]: http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17747

backpack

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 LeetCode BackPack 背包问题

相关 backpack

相关 [LeetCode] 322. Coin Change_Medium tag: backpack