完善程序1
小 到商店购物,她只带了 SW元钱。有 n件商品,第 i件商品的价格为 wi元,小 C对 它的满意度为vi 。小 想要知道,用自己仅有的 SW元钱,能买到的所有商品的满意度之 和最大是多少。
数据保证 1 ≤ n,wi,vi ≤100, 1 ≤ SW ≤ 10000
#include <iostream> using namespace std; const int INF = 0x3f3f3f3f; int n, SW, W[105], V[105], Dp[___(1)___]; int main() { cin >> n >> SW; for (int i = 1; i <= n; i++) cin >> W[i] >> V[i]; for (int i = 1; i <= SW; i++) Dp[i] = ___(2)___; for (int i = 1; i <= n; i++) for (___(3)___) Dp[j] = max(Dp[j], ___(4)___); int ans = 0; for (int i = 1; i <= SW; i++) ___(5)___; cout << ans << "\n"; return 0; }
(1) 处应填()
100
105
10000
10005
(2) 处应填()
INF
0
-1
1
(3) 处应填()
int j = SW; j >= W[i]; j--
int j = W[i]; j <= SW; j++
int j = 1; j <= n; j++
int j = n; j >= 1; j--
(4) 处应填()
Dp[i – W[j]] + V[j]
Dp[i – V[j]] + W[j]
Dp[j – W[i]] + V[i]
Dp[j – V[i]] + W[i]
(5) 处应填()
ans = max(ans, Dp[i])
ans = min(ans, Dp[i])
ans = ans + Dp[i]
ans = ans – Dp[i]
发表评论