問題描述
　　給定N個物品,每個物品有一個重量W和一個價值V.你有一個能裝M重量的背包.問怎么裝使得所裝價值最大.每個物品只有一個.
輸入格式
　　輸入的第一行包含兩個整數n, m，分別表示物品的個數和背包能裝重量。
　　以后N行每行兩個數Wi和Vi,表示物品的重量和價值
輸出格式
　　輸出1行，包含一個整數，表示最大價值。
樣例輸入
3 5
2 3
3 5
4 7
樣例輸出
8
數據規模和約定
　　1<=N<=200,M<=5000.

?

我的思路：

1. 01 背包問題，用了一維的解法

#include <iostream> #include <cmath> using namespace std;int weight[205], cost[205]; int n, m; int dp[205];int main() {scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++){scanf("%d %d", &weight[i], &cost[i]);}for(int i = 1; i <= n; i++){for(int v = m; v >= weight[i]; v--){dp[v] = max(dp[v], dp[v-weight[i]] + cost[i]);}}printf("%d",dp[m]);return 0; }

?

總結

以上是生活随笔為你收集整理的蓝桥杯 ADV-144 算法提高 01背包的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。