点击打开链接
思路:0/1背包
分析:
1 很明显的0/1背包
代码:
// 一维
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 30;
const int MAXN = 30010;
int total , m;
int v[N] , w[N];
int dp[MAXN];
int solve(){
for(int i = 1 ; i <= m ; i++){
for(int j = total ; j >= v[i] ; j--)
dp[j] = max(dp[j] , dp[j-v[i]]+v[i]*w[i]);
}
return dp[total];
}
int main(){
while(scanf("%d%d" , &total , &m) != EOF){
for(int i = 1 ; i <= m ; i++)
scanf("%d%d" , &v[i] , &w[i]);
memset(dp , 0 , sizeof(dp));
printf("%d\n" , solve());
}
return 0;
}
// 二维
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 30;
const int MAXN = 30010;
int total , m;
int v[N] , w[N];
int dp[N][MAXN];
int solve(){
memset(dp , 0 , sizeof(dp));
for(int i = 1 ; i <= m ; i++){
for(int j = total ; j >= 0 ; j--){
dp[i][j] = dp[i-1][j];
if(j >= v[i])
dp[i][j] = max(dp[i][j] , dp[i-1][j-v[i]]+v[i]*w[i]);
}
}
return dp[m][total];
}
int main(){
while(scanf("%d%d" , &total , &m) != EOF){
for(int i = 1 ; i <= m ; i++)
scanf("%d%d" , &v[i] , &w[i]);
printf("%d\n" , solve());
}
return 0;
}
分享到:
相关推荐
rqnoj的一些资料 c++的绝对对你有用。。。。。。
rqnoj ,题库。 密码锁(月赛) 动态规划,dp
很好的东西!省事省力省距离!免费啊免费啊
典型的排列组合题,几乎不需要什么解释。rqnoj第22题,程序写的很简练,初学者想想就懂了。
标程,有c++和Pascal版的。cena测试通过。RQNOJ测试通过。
Leetcode本项目使用的题库为 :star:主要使用Java书写算法,还有部分SQL语句练习,刚刚开始刷题,数量并不是很多 :grinning_face_with_sweat:我就不建翻译...TK题库 ATcoder 紫外线 RQNOJ YO玲珑学院 OJ彗星评测鸭 厨师