--Dirring love 音乐(01背包问题)

解题思路：

dp[i][j] 前 i 首歌放入 j 容量中的最大热情度。

前 i 首歌放到 j 容量中 dp[i][j]= dp[i-1][j-m[i]]+r[i] (注意：如果 j 容量 < m[i] 歌的大小则不能放，即 dp[i][j]=dp[i-1][j] )

不放 dp[i][j]=dp[i-1][j]

状态方程：

　　　　 dp[i][j]=max(dp[i-1][j],dp[i-1][j-m[i]]+r[i]);

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 //int m[105],r[105],dp[105][10005];
 4 int main()
 5 {
 6     int n,v;
 7     while(scanf("%d%d",&n,&v)!=EOF)
 8     {
 9         int m[n+2],r[n+2],dp[n+2][v+4];
10         memset(dp,0,sizeof(dp));
11         memset(m,0,sizeof(m));
12         memset(r,0,sizeof(r));
13         for(int i=1; i<=n; i++)scanf("%d%d",&m[i],&r[i]);
14 
15         for(int i=1; i<=n; i++)
16             for(int j=v; j>=0; j--)
17             {
18                 dp[i][j]=dp[i-1][j];
19                 if(j>=m[i])
20                     dp[i][j]=max(dp[i-1][j],dp[i-1][j-m[i]]+r[i]);
21             }
22         printf("%d
",dp[n][v]);
23     }
24     return 0;
25 }


优化空间复杂度：（降维）

#include<bits/stdc++.h>
using namespace std;
int main(void)
{
    int n,v;
    while(scanf("%d%d",&n,&v)!=EOF)
    {
        int m[n+4],r[n+4],dp[v+5];
        memset(m,0,sizeof(m));
        memset(r,0,sizeof(r));
        for(int i=0; i<n; i++)scanf("%d%d",&m[i],&r[i]);
        memset(dp,0,sizeof(dp));
        for(int i=0; i<=n; ++i)
            for(int j=v; j>=m[i]; j--)
                dp[j]= max(dp[j],dp[j-m[i]]+r[i]);
        printf("%d
",dp[v]);
    }
    return 0;
}

--Dirring love 音乐(01背包问题)

相关推荐