leetcode에서 가방 문제 사상으로 풀 수 있는 문제.

요 며칠 동안 배낭 문제를 복습하기 위해 내가 전에 쓴 블로그를 되돌아보고 leetcode 문제 연습 선수를 몇 개 찾았다.
leetcode에는 가방 문제에 대한 문제가 없지만 가방 생각으로 풀 수 있는 문제가 있습니다.
 
1、Coin Change(Leetcode 322)
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1 .(You may assume that you have an infinite number of each kind of coin.)
Example 1:
Input: coins = [1, 2, 5] , amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2] , amount = 3
Output: -1
즉, 서로 다른 액면가의 동전을 주고, 각 동전은 무수히 많으며, 총 액면가 amount를 하나 더 주고, 최소 몇 개의 동전으로 총 액면가를 구성할 수 있는지 물어본다.
아이디어:
동전 문제는 가방 문제와 같다. 동전의 액면가는 가방에 넣을 물건의 부피/무게/가치 등 속성으로 볼 수 있다.
이 문제에서 우리는 모아야 할 총 액면가를 하나의 가방의 총 용량으로 볼 수 있다. 즉, 우리의 가방은 무게가 amount인 것만 가장 많이 내려놓을 수 있다.모든 동전의 액면가를 이 동전의 무게로 간주한다면 우리는 문제를 총 용량이 amount인 가방에 최소한의 물건을 넣어 이 물건들의 총 무게가 가방의 최대 용량에 이르도록 하는 것으로 바꾸자.
요구에 따라 우리는 수조bag[w]를 설계하여 무게가 w인 가방에 최소 몇 개의 물품을 넣을 수 있도록 할 수 있다.우리의 최종 답은bag[amount]이다.bag[w], 1<=w<=amount에 대해 우리가 계산해야 할 것이고 우리가 찾으려는 것은 최소값이기 때문에 그들을 비교적 큰 값으로 초기화할 수 있다. 우리는 bag[w]=w를 동전의 액면가가 가장 작기 때문에 1이다.bag[0]에 대해 bag수조의 정의에 따라 알 수 있듯이 bag[0]=0.
다음에 우리는 어떻게 계산하는지 결정해야 한다bag[w].가령coin[i]이 i번째 동전의 액면가를 표시한다고 가정하면bag[w]=min(bag[w],min(bag[w-coin[i]))+1).우리는 물건을 가방에 하나씩 넣는 동전이 필요하다는 것을 이해할 수 있다.그래서 가방의 무게를 W로 하려면 가방의 무게가 W-coin[i]일 때 코인[i]의 물품을 넣어야 하기 때문에 bag[W]=bag[W-coin[i]+1(이곳의 1은 이 무게가 코인[i]인 물품을 가리킨다). 각 bag[W]를 최소화하려면 각 bag[W-coin[i]을 비교해야 한다(이곳의 코인[i]는 서로 다른 무게의 물품을 가리킨다).그리고 가장 작은 것을 취하고 하나를 더하고bag[w]와 비교한 다음에 가장 작은 값을 취한다.
코드:

class Solution {
public:
    int coinChange(vector& coins, int amount) {
        if(amount<1)
            return 0;
        vector bag(amount+1,amount+1);
        bag[0]=0;
        for(int v=1;v<=amount;++v)
            for(int coin:coins)
                if(v-coin>=0)
                    bag[v]=min(bag[v],bag[v-coin]+1);
        return (bag[amount]==amount+1)?-1:bag[amount];
        
    }
};

2、Coin Change 2(Leetcode 518) 
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Note:
You can assume that

0 <= amount <= 5000

1 <= coin <= 5000

the number of coins is less than 500

the answer is guaranteed to fit into signed 32-bit integer

Example 1:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
아이디어:
이 문제는 이전 문제의 문제를 액면가를 amount로 구성할 수 있는 몇 가지 방안으로 바꾸는 것이다.지난 문제는 이미 그렇게 많이 말했는데, 이 문제는 바로 핵심을 말한다.
문제의 정의에 따라bag[w]는 총액면가를 w로 모으려면 몇 가지 방안이 있을 수 있음을 나타낸다.분명히bag[w]=bag[w]+bag[w-coin[i]는 k종의 다른 방안을 위해 총 액면가가 w-coin[i]로 모을 수 있다면 이 k종의 다른 방안에coin[i]를 추가하면 총 액면가를 얻을 수 있는 w의 방안이다.
코드:

class Solution {
public:
    int change(int amount, vector& coins) {
        if(amount==0)
            return 1;
        vector bag(amount+1,0);
        bag[0]=1;
        for(int coin:coins)
            for(int v=coin;v<=amount;++v)
                bag[v]+=bag[v-coin];
        return bag[amount];
    }
};

 
3、Partition Equal Subset Sum(Leetcode 416)
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:

Each of the array element will not exceed 100.

The array size will not exceed 200.

Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
이 문제는 우리에게 비공정 정수 서열을 주고 이 서열을 두 원소의 총화와 같은 집합으로 나눌 수 있느냐는 것이다.
아이디어:
왜 이 문제를 가방 문제로 바꿀 수 있다고 말합니까?나는 이렇게 이해할 수 있다고 생각한다.
(1) 전체 서열을 알고 있다면 우리는 각 집합의 원소와 얼마를 계산해 낼 수 있다. =>가방의 총 용량cap
(2) 각 요소를 선택하여 두 컬렉션에 둘 요소를 결정합니다. =>아이템의 두 가지 상태: 가방에 넣는 것과 넣지 않는 것
그래서 문제는 n개 아이템 중 일부 아이템을 가방에 넣고 가방의 총 용량을cap로 할 수 있느냐는 것이다.
수조bag[w]를 설정하면 용량이 w인 가방은 가치가 얼마인 물품을 넣을 수 있는지 표시하고 서열에 있는 모든 원소ele를 무게와 가치가 같은 물품으로 간주한다.
코드:

class Solution {
public:
    bool canPartition(vector& nums) {
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum&1)
            return false;
        sum=(sum>>1);
        vector bag(sum+1,0);
        for(int w:nums)
            for(int v=sum;v>=w;--v)
                if(bag[v]

모든 물품이 한 번만 사용될 수 있도록 v=sum부터 계산해야 합니다.